×

Fast linear homotopy to find approximate zeros of polynomial systems. (English) Zbl 1232.65075

The authors consider the problem of finding an approximate zero of systems of polynomial equations and present a new algorithm which is based on the idea of homotopy methods. They prove the main theorem which states that the average running time of the algorithm is \(O(d^{3/2}nN(N+n^3))\), where \(N\) is the input size, \(n+1\) is the number of unknowns and \(d\) is the maximum of the degrees. Moreover, the average number of homotopy steps is at most \(Cd^{3/2}nN\), where \(C\leq 71\pi/\sqrt{2}\) is a constant. The authors show that the method can be applied to approximate several or all solutions of non-degenerate systems. The paper is very well written.

MSC:

65H10 Numerical computation of solutions to systems of equations
65H04 Numerical computation of roots of polynomial equations
65H20 Global methods, including homotopy approaches to the numerical solution of nonlinear equations
12Y05 Computational aspects of field theory and polynomials (MSC2010)
13P15 Solving polynomial systems; resultants
65Y20 Complexity and performance of numerical algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] E.L. Allgower, K. Georg, Numerical Continuation Methods (Springer, Berlin, 1990). · Zbl 0717.65030
[2] G.E. Andrews, R. Askey, R. Roy, Special Functions (Cambridge University Press, Cambridge, 1999). · Zbl 0920.33001
[3] D.J. Bates, J.D. Hauenstein, A.J. Sommese, C. Wampler, Bertini: software for numerical algebraic geometry, available at http://www.nd.edu/\(\sim\)sommese/bertini . · Zbl 1437.14005
[4] W. Baur, V. Strassen, The complexity of partial derivatives, Theor. Comput. Sci. 22(3), 317–330 (1983). · Zbl 0498.68028 · doi:10.1016/0304-3975(83)90110-X
[5] C. Beltrán, A continuation method to solve polynomial systems, and its complexity, Numer. Math. (2010). doi: 10.1007/s00211-010-0334-3 . · Zbl 1216.65058
[6] C. Beltrán, A. Leykin, Certified numerical homotopy tracking, to appear. arXiv:0912.0920 . · Zbl 1238.14048
[7] C. Beltrán, L.M. Pardo, On the complexity of non-universal polynomial equation solving: old and new results, in Foundations of Computational Mathematics: Santander 2005, ed. by L.-M. Pardo, A. Pinkus, E. Süli, M. Todd (Cambridge University Press, Cambridge, 2006), pp. 1–35. · Zbl 1107.65316
[8] C. Beltrán, L.M. Pardo, On Smale’s 17th problem: a probabilistic positive solution, Found. Comput. Math. 8(1), 1–43 (2008). · Zbl 1153.65048 · doi:10.1007/s10208-005-0211-0
[9] C. Beltrán, L.M. Pardo, Smale’s 17th problem: average polynomial time to compute affine and projective solutions, J. Am. Math. Soc. 22, 363–385 (2009). · Zbl 1206.90173 · doi:10.1090/S0894-0347-08-00630-9
[10] C. Beltrán, M. Shub, Complexity of Bézout’s Theorem VII: distance estimates in the condition metric, Found. Comput. Math. 9(2), 179–195 (2009). · Zbl 1175.65058 · doi:10.1007/s10208-007-9018-5
[11] C. Beltrán, M. Shub, A note on the finite variance of the averaging function for polynomial system solving, Found. Comput. Math. 10(1), 115–125 (2010). · Zbl 1192.65055 · doi:10.1007/s10208-009-9054-4
[12] L. Blum, M. Shub, S. Smale, On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines, Bull. Am. Math. Soc. (N.S.) 21(1), 1–46 (1989). · Zbl 0681.03020 · doi:10.1090/S0273-0979-1989-15750-9
[13] L. Blum, F. Cucker, M. Shub, S. Smale, Complexity and Real Computation (Springer, New York, 1998). · Zbl 0872.68036
[14] J. Bochnak, M. Coste, M.F. Roy, Géométrie algébrique réelle (Springer, Berlin, 1987).
[15] C.E. Borges, L.M. Pardo, On the probability distribution of data at points in real complete intersection varieties, J. Complex. 24, 492–523 (2008). · Zbl 1152.65056 · doi:10.1016/j.jco.2008.01.001
[16] P. Bürgisser, F. Cucker, On a problem posed by Steve Smale, Extended abstract in Proceedings STOC 2010, pp. 503–512. Full version: arXiv:0909.2114v5
[17] D. Castro, M. Giusti, J. Heintz, G. Matera, L.M. Pardo, The hardness of polynomial equation solving, Found. Comput. Math. 3(4), 347–420 (2003). · Zbl 1049.68070 · doi:10.1007/s10208-002-0065-7
[18] Z. Chen, J.J. Dongarra, Condition numbers of Gaussian random matrices, SIAM J. Matrix Anal. Appl. 27(3), 603–620 (2005). · Zbl 1107.15016 · doi:10.1137/040616413
[19] J.-P. Dedieu, G. Malajovich, M. Shub, Adaptative step size selection for homotopy methods to solve polynomial equations, to appear. · Zbl 1266.65080
[20] A. Edelman, Eigenvalues and condition numbers of random matrices, Ph.D. Thesis, Math. Dept. MIT, 1989. · Zbl 0678.15019
[21] A. Edelman, B. D Sutton, Tails of condition number distributions, SIAM J. Matrix Anal. Appl. 27(2), 547–560 (2005). · Zbl 1093.15010 · doi:10.1137/040614256
[22] R. Hartshorne, Algebraic Geometry (Springer, New York, 1977).
[23] T. L Lee, T.Y. Li, C.H. Tsai, Hom4ps-2.0: a software package for solving polynomial systems by the polyhedral homotopy continuation method, available at http://hom4ps.math.msu.edu/HOM4PS_soft.htm . · Zbl 1167.65366
[24] A. Leykin, Numerical algebraic geometry for Macaulay2, to appear. arXiv:0911.1783 . · Zbl 1311.14057
[25] S. Lojasiewicz, Introduction to Complex Analytic Geometry (Birkhäuser, Basel, 1991).
[26] J. Renegar, On the worst-case arithmetic complexity of approximating zeros of polynomials, J. Complex. 3(2), 90–113 (1987). · Zbl 0642.65031 · doi:10.1016/0885-064X(87)90022-7
[27] I.E. Segal, R.A. Kunze, Integrals and Operators, 2nd edn. (Springer, Berlin, 1978). · Zbl 0373.28001
[28] M. Shub, Some remarks on Bezout’s theorem and complexity theory, in From Topology to Computation: Proceedings of the Smalefest (Berkeley, CA), vol. 1990 (Springer, New York, 1993), pp. 443–455. · Zbl 0811.13021
[29] M. Shub, Complexity of Bézout’s theorem. VI: Geodesics in the condition (number) metric, Found. Comput. Math. 9(2), 171–178 (2009). · Zbl 1175.65060 · doi:10.1007/s10208-007-9017-6
[30] M. Shub, S. Smale, Complexity of Bézout’s theorem. I. Geometric aspects, J. Am. Math. Soc. 6(2), 459–501 (1993). · Zbl 0821.65035
[31] M. Shub, S. Smale, Complexity of Bezout’s theorem. II. Volumes and probabilities, in Computational Algebraic Geometry (Nice), vol. 1992 (Birkhäuser, Boston, 1993), pp. 267–285. · Zbl 0851.65031
[32] M. Shub, S. Smale, Complexity of Bezout’s theorem. V. Polynomial time, Theor. Comput. Sci. 133(1), 141–164 (1994). · Zbl 0846.65022 · doi:10.1016/0304-3975(94)90122-8
[33] M. Shub, S. Smale, Complexity of Bezout’s theorem. IV. Probability of success; extensions, SIAM J. Numer. Anal. 33(1), 128–148 (1996). · Zbl 0843.65035 · doi:10.1137/0733008
[34] S. Smale, Mathematical problems for the next century, in Mathematics: Frontiers and Perspectives (Amer. Math. Soc., Providence, 2000), pp. 271–294. · Zbl 1031.00005
[35] A.J. Sommese, C.W. Wampler II, The Numerical Solution of Systems of Polynomials (World Scientific, Hackensack, 2005). · Zbl 1091.65049
[36] J. Verschelde, Algorithm 795: PHCpack: a general-purpose solver for polynomial systems by homotopy continuation, ACM Trans. Math. Softw. 25(2), 251–276 (1999), available at http://www.math.uic.edu/\(\sim\)jan . · Zbl 0961.65047 · doi:10.1145/317275.317286
[37] J. Verschelde, Math review of ”On Smale’s 17th problem: a probabilistic positive solution” by C. Beltrán and L.M. Pardo. MR2403529 (2009h:65082) in Mathscinet.
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.