Artículo

Este artículo es de Acceso Abierto y puede ser descargado en su versión final desde nuestro repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

We present a symbolic probabilistic algorithm to compute the isolated roots in Cn of sparse polynomial equation systems. As some already known numerical algorithms solving this task, our procedure is based on polyhedral deformations and homotopies, but it amounts to solving a smaller number of square systems of equations and in fewer variables. The output of the algorithm is a geometric resolution of a finite set of points including the isolated roots of the system. The complexity is polynomial in the size of the combinatorial structure of the system supports up to a pre-processing yielding the mixed cells in a subdivision of the family of these supports. © 2010 Elsevier B.V. All rights reserved.

Registro:

Documento: Artículo
Título:Computing isolated roots of sparse polynomial systems in affine space
Autor:Herrero, M.I.; Jeronimo, G.; Sabia, J.
Filiación:Departamento de Matemtica, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Ciudad Universitaria, Pab. I, 1428 Buenos Aires, Argentina
Departamento de Ciencias Exactas, Ciclo Bsico Comn, Universidad de Buenos Aires, Ciudad Universitaria, Pab. III, 1428 Buenos Aires, Argentina
Palabras clave:Algorithms; Complexity; Sparse polynomial systems; Affine space; Combinatorial structures; Complexity; Finite set; Geometric resolution; Homotopies; Numerical algorithms; Pre-processing; Probabilistic algorithm; Sparse polynomials; System supports; Systems of equations; Algorithms; Topology; Polynomials
Año:2010
Volumen:411
Número:44-46
Página de inicio:3894
Página de fin:3904
DOI: http://dx.doi.org/10.1016/j.tcs.2010.07.015
Título revista:Theoretical Computer Science
Título revista abreviado:Theor Comput Sci
ISSN:03043975
CODEN:TCSCD
PDF:https://bibliotecadigital.exactas.uba.ar/download/paper/paper_03043975_v411_n44-46_p3894_Herrero.pdf
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03043975_v411_n44-46_p3894_Herrero

Referencias:

  • Basu, S., Pollack, R., Roy, M.-F., Algorithms in Real Algebraic Geometry (2006) Algorithms and Computation in Mathematics, 10. , 2nd ed. Springer-Verlag Berlin
  • Bernstein, D.N., The number of roots of a system of equations (1975) Funct. Anal. Appl., 9, pp. 183-185
  • Cox, D., Little, J., O'Shea, D., Using algebraic geometry (1998) Graduate Texts in Mathematics, Vol. 185, , Springer New York
  • Emiris, I.Z., Canny, J.F., Efficient incremental algorithms for the sparse resultant and the mixed volume (1995) J. Symbolic Comput., 20 (2), pp. 117-149
  • Emiris, I.Z., Verschelde, J., How to count efficiently all affine roots of a polynomial system (1999) Discrete Appl. Math., 93 (1), pp. 21-32
  • Gao, T., Li, T.Y., Mixed volume computation for semi-mixed systems (2003) Discrete Comput. Geom., 29 (2), pp. 257-277
  • Gao, T., Li, T.Y., Wang, X., Finding all isolated zeroes of polynomial systems in Cn via stable mixed volumes. Polynomial eliminationalgorithms and applications (1999) J. Symbolic Comput., 28 (12), pp. 187-211
  • Von Zur Gathen, J., Gerhard, J., (1999) Modern Computer Algebra, , Cambridge University Press Cambridge
  • Gelfand, I.M., Kapranov, M.M., Zelevinsky, A.V., Discriminants, resultants, and multidimensional determinants (1994) Mathematics: Theory & Applications, , Birkhuser Boston, Inc. Boston, MA
  • 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, pp. 101-146
  • Giusti, M., Lecerf, G., Salvy, B., A Grbner free alternative for polynomial system solving (2001) J. Complexity, 17 (1), pp. 154-211
  • Heintz, J., Krick, T., Puddu, S., Sabia, J., Waissbein, A., Deformation techniques for efficient polynomial equation solving (2000) J. Complex., 16 (1), pp. 70-109
  • Huber, B., Sturmfels, B., A polyhedral method for solving sparse polynomial systems (1995) Math. Comput., 64 (212), pp. 1541-1555
  • Huber, B., Sturmfels, B., Bernstein's theorem in affine space (1997) Discrete Comput. Geom., 17, pp. 137-141
  • Jeronimo, G., Krick, T., Sabia, J., Sombra, M., The computational complexity of the Chow form, Found (2004) Comput. Math., 4 (1), pp. 41-117
  • Jeronimo, G., Matera, G., Solern, P., Waissbein, A., Deformation techniques for sparse systems (2009) Found. Comput. Math., 9, pp. 1-50
  • Khovanskii, A.G., Newton polyhedra and toroidal varieties (1978) Funct. Anal. Appl., 11, pp. 289-296
  • Kushnirenko, A.G., Newton polytopes and the Bezout theorem (1976) Funct. Anal. Appl., 10, pp. 233-235
  • Lecerf, G., Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers (2003) J. Complex., 19 (4), pp. 564-596
  • Li, T.Y., Numerical solution of multivariate polynomial systems by homotopy continuation methods (1997) Acta Numer., 6, pp. 399-436
  • Li, T.Y., Li, X., Finding mixed cells in the mixed volume computation (2001) Found. Comput. Math., 1 (2), pp. 161-181
  • Li, T.Y., Wang, X., The BKK root count in Cn (1996) Math. Comp., 65 (216), pp. 1477-1484
  • Mizutani, T., Takeda, A., Kojima, M., Dynamic enumeration of all mixed cells (2007) Discrete Comput. Geom., 37 (3), pp. 351-367
  • Rojas, J.M., A convex geometrical approach to counting the roots of a polynomial system (1994) Theoret. Comput. Sci., 133, pp. 105-140
  • Rojas, J.M., Why polyhedra matter in non-linear equation solving (2003) Contemp. Math., 334, pp. 293-320. , Topics in Algebraic Geometry and Geometric Modeling, Amer. Math. Soc. Providence, RI
  • Rojas, J.M., Wang, X., Counting affine roots of polynomial systems via pointed Newton polytopes (1996) J. Complexity, 12 (2), pp. 116-133
  • Sommese, A., Wampler, C., (2005) The Numerical Solution of Systems of Polynomials Arising in Engineering and Science, , World Scientific Singapore
  • Verschelde, J., Gatermann, K., Cools, R., Mixed-volume computation by dynamic lifting applied to polynomial system solving (1996) Discrete Comput. Geom., 16 (1), pp. 69-112
  • Verschelde, J., Verlinden, P., Cools, R., Homotopies exploiting Newton polytopes for solving sparse polynomial systems (1994) SIAM J. Numer. Anal., 31 (3), pp. 915-930
  • Walker, R., (1978) Algebraic Curves, , Springer

Citas:

---------- APA ----------
Herrero, M.I., Jeronimo, G. & Sabia, J. (2010) . Computing isolated roots of sparse polynomial systems in affine space. Theoretical Computer Science, 411(44-46), 3894-3904.
http://dx.doi.org/10.1016/j.tcs.2010.07.015
---------- CHICAGO ----------
Herrero, M.I., Jeronimo, G., Sabia, J. "Computing isolated roots of sparse polynomial systems in affine space" . Theoretical Computer Science 411, no. 44-46 (2010) : 3894-3904.
http://dx.doi.org/10.1016/j.tcs.2010.07.015
---------- MLA ----------
Herrero, M.I., Jeronimo, G., Sabia, J. "Computing isolated roots of sparse polynomial systems in affine space" . Theoretical Computer Science, vol. 411, no. 44-46, 2010, pp. 3894-3904.
http://dx.doi.org/10.1016/j.tcs.2010.07.015
---------- VANCOUVER ----------
Herrero, M.I., Jeronimo, G., Sabia, J. Computing isolated roots of sparse polynomial systems in affine space. Theor Comput Sci. 2010;411(44-46):3894-3904.
http://dx.doi.org/10.1016/j.tcs.2010.07.015