Artículo

Bank, B.; Giusti, M.; Heintz, J.; Lecerf, G.; Matera, G.; Solernó, P. "Degeneracy Loci and Polynomial Equation Solving" (2014) Foundations of Computational Mathematics. 15(1):159-184
Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

Let (Formula presented.) be a smooth, equidimensional, quasi-affine variety of dimension (Formula presented.) over (Formula presented.), and let (Formula presented.) be a (Formula presented.) matrix of coordinate functions of (Formula presented.), where (Formula presented.). The pair (Formula presented.) determines a vector bundle (Formula presented.) of rank (Formula presented.) over (Formula presented.). We associate with (Formula presented.) a descending chain of degeneracy loci of (Formula presented.) (the generic polar varieties of (Formula presented.) represent a typical example of this situation). The maximal degree of these degeneracy loci constitutes the essential ingredient for the uniform, bounded-error probabilistic pseudo-polynomial-time algorithm that we will design and that solves a series of computational elimination problems that can be formulated in this framework. We describe applications to polynomial equation solving over the reals and to the computation of a generic fiber of a dominant endomorphism of an affine space. © 2014, SFoCM.

Registro:

Documento: Artículo
Título:Degeneracy Loci and Polynomial Equation Solving
Autor:Bank, B.; Giusti, M.; Heintz, J.; Lecerf, G.; Matera, G.; Solernó, P.
Filiación:Institut für Mathematik, Humboldt-Universität zu Berlin, Berlin, 10099, Germany
Laboratoire d’informatique, LIX, UMR 7161 CNRS, Campus de l’École Polytechnique, Palaiseau Cedex, 91128, France
Departamento de Computación, Universidad de Buenos Aires, Ciudad Univ., Pab.I, Buenos Aires, 1428, Argentina
CONICET, Ciudad Univ., Pab.I, Buenos Aires, 1428, Argentina
Departamento de Matemáticas, Estadística y Computación, Universidad de Cantabria, Santander, 39071, Spain
Instituto del Desarrollo Humano, Universidad Nacional de General Sarmiento, J. M. Gutierrez 1150, Los Polvorines, Buenos Aires, B1613GSX, Argentina
CONICET, J. M. Gutierrez 1150, Los Polvorines, Buenos Aires, B1613GSX, Argentina
Instituto Matemático Luis Santaló, CONICET, Buenos Aires, 1428, Argentina
Departamento de Matemáticas, Universidad de Buenos Aires, Buenos Aires, 1428, Argentina
Palabras clave:Degeneracy locus; Degree of varieties; Polynomial equation solving; Pseudo-polynomial complexity; Algorithms; Coordinate functions; Degeneracy loci; Degree of varieties; Descending chain; Elimination problem; Polynomial complexity; Polynomial equation solving; Polynomial-time algorithms; Polynomial approximation
Año:2014
Volumen:15
Número:1
Página de inicio:159
Página de fin:184
DOI: http://dx.doi.org/10.1007/s10208-014-9214-z
Título revista:Foundations of Computational Mathematics
Título revista abreviado:Found. Comput. Math.
ISSN:16153375
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_16153375_v15_n1_p159_Bank

Referencias:

  • Bank, B., Giusti, M., Heintz, J., Lehmann, L., Pardo, L.M., Algorithms of intrinsic complexity for point searching in compact real singular hypersurfaces, Found (2012) Comput. Math, 12 (1), pp. 75-122
  • Bank, B., Giusti, M., Heintz, J., Mbakop, G.M., Polar varieties and efficient real elimination (2001) Math. Z, 238 (1), pp. 115-144
  • Bank, B., Giusti, M., Heintz, J., Pardo, L.M., Generalized polar varieties and an efficient real elimination (2004) Kybernetika, 40 (5), pp. 519-550
  • Bank, B., Giusti, M., Heintz, J., Pardo, L.M., Generalized polar varieties: geometry and algorithms (2005) J. Complexity, 21 (4), pp. 377-412
  • Bank, B., Giusti, M., Heintz, J., Safey El Din, M., Schost, É., On the geometry of polar varieties (2010) Appl. Algebra Eng. Commun. Comput, 21 (1), pp. 33-83
  • Bruns, W., Vetter, U., Determinantal rings, Lecture Notes in Mathematics, vol. 1327 (1988) Springer Berlin Heidelberg
  • Bürgisser, P., Clausen, M., Shokrollahi, M.A., Algebraic complexity theory, Grundlehren der mathematischen Wissenschaften, vol. 315 (1997) Springer Berlin Heidelberg
  • Bürgisser, P., Lotz, M., The complexity of computing the Hilbert polynomial of smooth equidimensional complex projective varieties, Found (2007) Comput.Math., 7 (1), pp. 59-86
  • Cafure, A., Matera, G., Fast computation of a rational point of a variety over a finite field (2006) Math. Comp, 75 (256), pp. 2049-2085
  • Demazure, M., (1989) Catastrophes et bifurcations, , Ellipses, Paris
  • Durvye, C., Lecerf, G., A concise proof of the Kronecker polynomial system solver from scratch, Expo (2008) Math, 26 (2), pp. 101-139
  • J. A. Eagon and M. Hochster(Formula presented.)-sequences and indeterminates, Quart. J. Math. Oxford Ser. (2) 25 (1974), 61–71; Eagon, J.A., Northcott, D.G., Ideals defined by matrices and a certain complex associated with them (1962) Proc. Roy. Soc. Ser. A, 269, pp. 188-204
  • Eisenbud, D., Commutative algebra with a view toward algebraic geometry (1995) Graduate Texts in Mathematics, 150. , Springer-Verlag, New York
  • Faugère, J.-C., FGb: A Library for Computing Gröbner Bases, Mathematical Software - ICMS 2010 (K. Fukuda, J. van der Hoeven, M. Joswig, and N. Takayama, eds.), Lecture Notes in Comput. Sci. vol. 6327 Springer-Verlag, 2010, pp. 84-87
  • Fulton, W., Intersection theory, second ed. Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge (1998) A Series of Modern Surveys in Mathematics, 2. , Springer-Verlag, Berlin
  • Giusti, M., Heintz, J., Hägele, K., Morais, J.E., Pardo, L.M., Montaña, J.L., Lower bounds for Diophantine approximations (1997) J. Pure Appl. Algebra, 117, pp. 277-317
  • Giusti, M., Heintz, J., Morais, J.E., Morgenstern, J., Pardo, L.M., Straight-line programs in geometric elimination theory (1998) J. Pure Appl. Algebra, 124 (1-3), pp. 101-146
  • Giusti, M., Lecerf, G., Salvy, B., A Gröbner free alternative for polynomial system solving (2001) J. Complexity, 17 (1), pp. 154-211
  • Heintz, J., Definability and fast quantifier elimination in algebraically closed fields, Theoret (1983) Comput. Sci, 24 (3), pp. 239-277
  • Heintz, J., Matera, G., Waissbein, A., On the time-space complexity of geometric elimination procedures (2001) Appl. Algebra Engrg. Comm. Comput, 11 (4), pp. 239-296
  • Heintz and C.-P. Schnorr, Testing polynomials which are easy to compute, International Symposium on Logic and Algorithmic (Zurich, 1980) (Geneva), Monograph. Enseign. Math. vol. 30, Univ (1982) Genève, pp. 237-254
  • E. Kaltofen and B. D. Saunders, On Wiedemann’s method of solving sparse linear systems, Applied algebra, algebraic algorithms and error-correcting codes (New Orleans, LA, 1991), Lecture Notes in Comput. Sci., vol. 539, Springer, Berlin, 1991, pp. 29–38; Matsumura, H., (1986) Cambridge Studies in Advanced Mathematics, 8. , Cambridge University Press, Cambridge, Translated from the Japanese by M. Reid
  • Mumford, D., Springer-Verlag Berlin, p. 1988
  • Piene, R., Polar classes of singular varieties (1978) Ann. Sci. École Norm. Sup. (4), 11 (2), pp. 247-276
  • http://www-polsys.lip6.fr/~safey/RAGLib, M. Safey El Din, RAGLib (Real Algebraic Geometry Library), Maple (TM) package, from 2007; Safey El Din, M., Trébuchet, P., Strong bi-homogeneous Bézout theorem and its use in effective real algebraic geometry, Tech. Report 6001 (2006) INRIA, , http://hal.inria.fr/inria-00105204
  • Schwartz, J.T., Fast probabilistic algorithms for verification of polynomial identities (1980) J. Assoc. Comput. Mach, 27 (4), pp. 701-717
  • Shafarevich, I.R., algebraic, B., Varieties in projective space (1994) Translated from the 1988 Russian edition and with notes by Miles Reid
  • Shafarevich, I.R., algebraic, B., Schemes and complex manifolds (1994) Translated from the 1988 Russian edition by Miles Reid
  • Turrel Bardet, M., (2004) Ph.D. thesis, Université Paris, p. 6. , http://tel.archives-ouvertes.fr/tel-00449609
  • van der Hoeven, J., Lecerf, G., Mourain, B., Mathemagix (2002) from, , http://www.mathemagix.org
  • Vogel, W., (1984) Lectures on results on Bezout’s theorem, Tata Institute of Fundamental Research Lectures on Mathematics and Physics, 74. , Published for the Tata Institute of Fundamental Research, Bombay, Notes by D. P. Patil
  • Zippel, R., Probabilistic algorithms for sparse polynomials, Symbolic and algebraic computation (EUROSAM ’79, Internat. Sympos. Marseille (1979) Lecture Notes in Comput. Sci., vol. 72, Springer, Berlin, 1979, pp. 216-226

Citas:

---------- APA ----------
Bank, B., Giusti, M., Heintz, J., Lecerf, G., Matera, G. & Solernó, P. (2014) . Degeneracy Loci and Polynomial Equation Solving. Foundations of Computational Mathematics, 15(1), 159-184.
http://dx.doi.org/10.1007/s10208-014-9214-z
---------- CHICAGO ----------
Bank, B., Giusti, M., Heintz, J., Lecerf, G., Matera, G., Solernó, P. "Degeneracy Loci and Polynomial Equation Solving" . Foundations of Computational Mathematics 15, no. 1 (2014) : 159-184.
http://dx.doi.org/10.1007/s10208-014-9214-z
---------- MLA ----------
Bank, B., Giusti, M., Heintz, J., Lecerf, G., Matera, G., Solernó, P. "Degeneracy Loci and Polynomial Equation Solving" . Foundations of Computational Mathematics, vol. 15, no. 1, 2014, pp. 159-184.
http://dx.doi.org/10.1007/s10208-014-9214-z
---------- VANCOUVER ----------
Bank, B., Giusti, M., Heintz, J., Lecerf, G., Matera, G., Solernó, P. Degeneracy Loci and Polynomial Equation Solving. Found. Comput. Math. 2014;15(1):159-184.
http://dx.doi.org/10.1007/s10208-014-9214-z