×

Computing isolated roots of sparse polynomial systems in affine space. (English) Zbl 1241.65046

The subject of this paper concerns solving – numerically and symbolically – polynomial equation systems over \(\mathbb{C}^*\). Because actual efficient algorithms are based on the polyhedral deformations proposed by T. Gao, T. Y. Li and X. Wang [J. Symb. Comput. 28, No. 1–2, 187–211 (1999; Zbl 0944.65055)] (which preserve the monomial structure of the system), it results that the number of variants obtained by deformation equals the expected number of solutions. For sparse systems that means algorithms of lower complexity.
The main result of the paper is focused in the theorem: Let \(f_1,\dots,f_n\) be polynomials in \(\mathbb{Q}[X_1,\dots,X_n]\). There exists a probabilistic algorithm which computes a finite set of points containing the isolated common zeros of \(f_1,\dots,f_n\) in \(\mathbb{C}^n\) within a complexity which is polynomial in the size of the combinatorial structure of the system supports.
The algorithm – detailed, analyzed by its complexity and exemplified – is called AffineSolve and it improves the algorithm proposed by G. Jeronimo, G. Matera, P. Solernó and A. Waissbein [Found. Comput. Math. 9, No. 1, 1–50 (2009; Zbl 1167.14039)].
Although it is not mentioned in the paper, this result can be used in several other domains which are based on solving polynomial equation systems, like coding theory or dynamical systems.

MSC:

65H10 Numerical computation of solutions to systems of equations
65H04 Numerical computation of roots of polynomial equations
12D10 Polynomials in real and complex fields: location of zeros (algebraic theorems)
03D15 Complexity of computation (including implicit computational complexity)
65Y20 Complexity and performance of numerical algorithms
68W30 Symbolic computation and algebraic computation

Software:

DEMiCs; Kronecker
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Basu, S.; Pollack, R.; Roy, M.-F., (Algorithms in Real Algebraic Geometry. Algorithms in Real Algebraic Geometry, Algorithms and Computation in Mathematics, vol. 10 (2006), Springer-Verlag: Springer-Verlag Berlin) · Zbl 1102.14041
[2] Bernstein, D. N., The number of roots of a system of equations, Funct. Anal. Appl., 9, 183-185 (1975), Translated from Funkts. Anal. Prilozh. 9(3) (1975) 1-4 · Zbl 0328.32001
[3] Cox, D.; Little, J.; O’Shea, D., Using algebraic geometry, (Graduate Texts in Mathematics, vol. 185 (1998), Springer: Springer New York) · Zbl 0920.13026
[4] Emiris, I. Z.; Canny, J. F., Efficient incremental algorithms for the sparse resultant and the mixed volume, J. Symbolic Comput., 20, 2, 117-149 (1995) · Zbl 0843.68036
[5] Emiris, I. Z.; Verschelde, J., How to count efficiently all affine roots of a polynomial system, Discrete Appl. Math., 93, 1, 21-32 (1999) · Zbl 1034.68715
[6] Gao, T.; Li, T. Y., Mixed volume computation for semi-mixed systems, Discrete Comput. Geom., 29, 2, 257-277 (2003) · Zbl 1052.68131
[7] Gao, T.; Li, T. Y.; Wang, X., Finding all isolated zeroes of polynomial systems in \(C^n\) via stable mixed volumes. Polynomial elimination—algorithms and applications, J. Symbolic Comput., 28, 1-2, 187-211 (1999) · Zbl 0944.65055
[8] von zur Gathen, J.; Gerhard, J., Modern Computer Algebra (1999), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0936.11069
[9] Gelfand, I. M.; Kapranov, M. M.; Zelevinsky, A. V., Discriminants, resultants, and multidimensional determinants, (Mathematics: Theory & Applications (1994), Birkhäuser Boston, Inc.: Birkhäuser Boston, Inc. Boston, MA) · Zbl 0827.14036
[10] Giusti, M.; Heintz, J.; Morais, J. E.; Morgenstern, J.; Pardo, L. M., Straight-line programs in geometric elimination theory, J. Pure Appl. Algebra, 124, 101-146 (1998) · Zbl 0944.12004
[11] Giusti, M.; Lecerf, G.; Salvy, B., A Gröbner free alternative for polynomial system solving, J. Complexity, 17, 1, 154-211 (2001) · Zbl 1003.12005
[12] Heintz, J.; Krick, T.; Puddu, S.; Sabia, J.; Waissbein, A., Deformation techniques for efficient polynomial equation solving, J. Complex., 16, 1, 70-109 (2000) · Zbl 1041.65044
[13] Huber, B.; Sturmfels, B., A polyhedral method for solving sparse polynomial systems, Math. Comput., 64, 212, 1541-1555 (1995) · Zbl 0849.65030
[14] Huber, B.; Sturmfels, B., Bernstein’s theorem in affine space, Discrete Comput. Geom., 17, 137-141 (1997) · Zbl 0891.65055
[15] Jeronimo, G.; Krick, T.; Sabia, J.; Sombra, M., The computational complexity of the Chow form, Found, Comput. Math., 4, 1, 41-117 (2004) · Zbl 1058.14075
[16] Jeronimo, G.; Matera, G.; Solernó, P.; Waissbein, A., Deformation techniques for sparse systems, Found. Comput. Math., 9, 1-50 (2009) · Zbl 1167.14039
[17] Khovanskii, A. G., Newton polyhedra and toroidal varieties, Funct. Anal. Appl., 11, 289-296 (1978) · Zbl 0445.14019
[18] Kushnirenko, A. G., Newton polytopes and the Bezout theorem, Funct. Anal. Appl., 10, 233-235 (1976) · Zbl 0341.32001
[19] Lecerf, G., Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers, J. Complex., 19, 4, 564-596 (2003) · Zbl 1230.68222
[20] Li, T. Y., Numerical solution of multivariate polynomial systems by homotopy continuation methods, Acta Numer., 6, 399-436 (1997) · Zbl 0886.65054
[21] Li, T. Y.; Li, X., Finding mixed cells in the mixed volume computation, Found. Comput. Math., 1, 2, 161-181 (2001) · Zbl 1012.65019
[22] Li, T. Y.; Wang, X., The BKK root count in \(C^n\), Math. Comp., 65, 216, 1477-1484 (1996) · Zbl 0855.65053
[23] Mizutani, T.; Takeda, A.; Kojima, M., Dynamic enumeration of all mixed cells, Discrete Comput. Geom., 37, 3, 351-367 (2007) · Zbl 1113.65055
[24] Rojas, J. M., A convex geometrical approach to counting the roots of a polynomial system, Theoret. Comput. Sci., 133, 105-140 (1994) · Zbl 0812.65040
[25] Rojas, J. M., Why polyhedra matter in non-linear equation solving, (Topics in Algebraic Geometry and Geometric Modeling. Topics in Algebraic Geometry and Geometric Modeling, Contemp. Math., vol. 334 (2003), Amer. Math. Soc.: Amer. Math. Soc. Providence, RI), 293-320 · Zbl 1073.12007
[26] Rojas, J. M.; Wang, X., Counting affine roots of polynomial systems via pointed Newton polytopes, J. Complexity, 12, 2, 116-133 (1996) · Zbl 0885.12007
[27] Sommese, A.; Wampler, C., The Numerical Solution of Systems of Polynomials Arising in Engineering and Science (2005), World Scientific: World Scientific Singapore · Zbl 1091.65049
[28] Verschelde, J.; Gatermann, K.; Cools, R., Mixed-volume computation by dynamic lifting applied to polynomial system solving, Discrete Comput. Geom., 16, 1, 69-112 (1996) · Zbl 0854.68111
[29] Verschelde, J.; Verlinden, P.; Cools, R., Homotopies exploiting Newton polytopes for solving sparse polynomial systems, SIAM J. Numer. Anal., 31, 3, 915-930 (1994) · Zbl 0809.65048
[30] Walker, R., Algebraic Curves (1978), Springer
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.