×

Robust certified numerical homotopy tracking. (English) Zbl 1267.14075

The authors describe an algorithmic scheme for the linear homotopy method in solving systems of polynomial equations. The linear bit length complexity of the algorithm is established. Two computational experimental results of the algorithm are presented. One of them involves a small family of equations, and the other comes from an application in enumerative geometry.

MSC:

14Q20 Effectivity, complexity and computational aspects of algebraic geometry
65H20 Global methods, including homotopy approaches to the numerical solution of nonlinear equations
68W30 Symbolic computation and algebraic computation
PDF BibTeX XML Cite
Full Text: DOI arXiv Link

References:

[1] Bates, D.J.; Peterson, C.; Sommese, A.J.; Wampler, C.W., Numerical computation of the genus of an irreducible curve within an algebraic set, J. Pure Appl. Algebra, 215, 1844-1851, (2011) · Zbl 1211.14062
[2] D.J. Bates, J.D. Hauenstein, A.J. Sommese, C.W. Wampler, Bertini: software for numerical algebraic geometry. Available at http://www.nd.edu/ sommese/bertini. · Zbl 1143.65344
[3] Baur, W.; Strassen, V., The complexity of partial derivatives, Theor. Comput. Sci., 22, 317-330, (1983) · Zbl 0498.68028
[4] Beltrán, C., A continuation method to solve polynomial systems, and its complexity, Numer. Math., 117, 89-113, (2011) · Zbl 1216.65058
[5] Beltrán, C.; Leykin, A., Certified numerical homotopy tracking, Exp. Math., 21, 69-83, (2012) · Zbl 1238.14048
[6] Beltrán, C.; Pardo, L.M., On smale’s 17th problem: a probabilistic positive solution, Found. Comput. Math., 8, 1-43, (2008) · Zbl 1153.65048
[7] Beltrán, C.; Pardo, L.M., Smale’s 17th problem: average polynomial time to compute affine and projective solutions, J. Am. Math. Soc., 22, 363-385, (2009) · Zbl 1206.90173
[8] Beltrán, C.; Pardo, L.M., Fast linear homotopy to find approximate zeros of polynomial systems, Found. Comput. Math., 11, 95-129, (2011) · Zbl 1232.65075
[9] Billey, S.; Vakil, R.; Dickenstein, A. (ed.); Schreyer, F.O. (ed.); Sommese, A.J. (ed.), Intersections of Schubert varieties and other permutation array schemes, No. 146, 21-54, (2008), New York · Zbl 1132.14044
[10] Blum, L.; Shub, M.; Smale, S., On a theory of computation and complexity over the real numbers; NP completeness, recursive functions and universal machines, Bull. Am. Math. Soc., 21, 1-46, (1989) · Zbl 0681.03020
[11] L. Blum, F. Cucker, M. Shub, S. Smale, Complexity and Real Computation (Springer, New York, 1998). · Zbl 0872.68036
[12] Bürguisser, P.; Cucker, F., On a problem posed by steve Smale, Ann. Math., 174, 1785-1836, (2011) · Zbl 1248.65047
[13] Castro, D.; Hägele, K.; Morais, J.E.; Pardo, L.M., Kronecker’s and newton’s approaches to solving: a first comparison, J. Complex., 17, 212-303, (2001) · Zbl 1013.68296
[14] Castro, D.; Montaña, J.L.; Pardo, L.M.; San Martín, J., The distribution of condition numbers of rational data of bounded bit length, Found. Comput. Math., 2, 1-52, (2002) · Zbl 1011.65017
[15] T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms (MIT Press, Cambridge, 1990). · Zbl 1158.68538
[16] Dedieu, J.-P.; Malajovich, G.; Shub, M., Adaptative step size selection for homotopy methods to solve polynomial equations, IMA J. Numer. Anal., (2010) · Zbl 1266.65080
[17] Dixon, J.D., Exact solution of linear equations using \(p\)-adic expansions, Numer. Math., 40, 137-141, (1982) · Zbl 0492.65016
[18] D.R. Grayson, M.E. Stillman, Macaulay 2, a software system for research in algebraic geometry. Available at http://www.math.uiuc.edu/Macaulay2/. · Zbl 0809.65050
[19] J.D. Hauenstein, F. Sottile, alphacertified: certifying solutions to polynomial systems (2010). arXiv:1011.1091v1. · Zbl 1365.65148
[20] Kearfott, R.B.; Xing, Z., An interval step control for continuation methods, SIAM J. Numer. Anal., 31, 892-914, (1994) · Zbl 0809.65050
[21] M.H. Kim, Computational complexity of the Euler type algorithms for the roots of complex polynomials. Ph.D. Thesis, The City University of New York, 1985. · Zbl 0492.65016
[22] 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
[23] Leykin, A., Numerical algebraic geometry for macaulay2, J. Softw. Algebr. Geom., 3, 5-10, (2011) · Zbl 1311.14057
[24] Leykin, A.; Sottile, F., Galois groups of Schubert problems via homotopy computation, Math. Comput., 78, 1749-1765, (2009) · Zbl 1210.14064
[25] G. Malajovich, On the complexity of path-following Newton algorithms for solving systems of polynomial equations with integer coefficients. Ph.D. Thesis, Univ. California, Berkley, 1993. · Zbl 0492.65016
[26] Malajovich, G., On generalized Newton algorithms: quadratic convergence, path-following and error analysis, Theor. Comput. Sci., 133, 65-84, (1994) · Zbl 0811.65039
[27] Malajovich, G., Condition number bounds for problems with integer coefficients, J. Complex., 16, 529-551, (2000) · Zbl 0974.65039
[28] G. Malajovich, PSS—Polynomial System Solver version 3.0.5. Available at. http://www.labma.ufrj.br/ gregorio/software.php. · Zbl 1206.90173
[29] C.H. Papadimitriou, Computational Complexity (Addison-Wesley, Reading, 1994). · Zbl 0833.68049
[30] Shub, M.; Hirsch, M.W. (ed.); Marsden, J.E. (ed.); Shub, M. (ed.), Some remarks on bezout’s theorem and complexity theory, 443-455, (1993), New York · Zbl 0811.13021
[31] Shub, M., Complexity of Bézout’s theorem. VI: geodesics in the condition (number) metric, Found. Comput. Math., 9, 171-178, (2009) · Zbl 1175.65060
[32] Shub, M.; Smale, S.; Eyssette, Fr. (ed.); Galligo, A. (ed.), Complexity of Bézout’s theorem. II. volumes and probabilities, No. 109, 267-285, (1993), Boston · Zbl 0851.65031
[33] Shub, M.; Smale, S., Complexity of Bézout’s theorem. I. geometric aspects, J. Am. Math. Soc., 6, 459-501, (1993) · Zbl 0821.65035
[34] Shub, M.; Smale, S., Complexity of bezout’s theorem. V. polynomial time, Barcelona, 1993 · Zbl 0846.65022
[35] Smale, S., The fundamental theorem of algebra and complexity theory, Bull. Am. Math. Soc., 4, 1-36, (1981) · Zbl 0456.12012
[36] Smale, S., Newton’s method estimates from data at one point, 185-196, (1986), New York
[37] J. van der Hoeven, Reliable homotopy continuation. Technical Report, HAL 00589948 (2011).
[38] Verschelde, J., Algorithm 795: phcpack: a general-purpose solver for polynomial systems by homotopy continuation, ACM Trans. Math. Softw., 25, 251-276, (1999) · Zbl 0961.65047
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.