×

Certified predictor-corrector tracking for Newton homotopies. (English) Zbl 1329.65110

Summary: We develop certified tracking procedures for Newton homotopies, which are homotopies for which only the constant terms are changed. For these homotopies, our certified procedures include using a constant predictor with Newton corrections, an Euler predictor with no corrections, and an Euler predictor with Newton corrections. In each case, the predictor is guaranteed to produce a point in the quadratic convergence basin of Newton’s method. We analyze the complexity of a tracking procedure using a constant predictor with Newton corrections, with the number of steps bounded above by a constant multiple of the length of the path in the \(\gamma\)-metric. Examples are included to compare the behavior of these certified tracking methods.

MSC:

65H20 Global methods, including homotopy approaches to the numerical solution of nonlinear equations
65H10 Numerical computation of solutions to systems of equations
65H04 Numerical computation of roots of polynomial equations
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Bates, D. J.; Hauenstein, J. D.; Sommese, A. J., Efficient path tracking methods, Numer. Algorithms, 58, 4, 451-459, (2011) · Zbl 1230.65059
[2] Bates, D. J.; Hauenstein, J. D.; Sommese, A. J.; Wampler, C. W., Bertini: software for numerical algebraic geometry, (2006), Available at
[3] Beltrán, C.; Leykin, A., Certified numerical homotopy tracking, Exp. Math., 21, 69-83, (2012) · Zbl 1238.14048
[4] Beltrán, C.; Leykin, A., Robust certified numerical homotopy tracking, Found. Comput. Math., 13, 2, 253-295, (2013) · Zbl 1267.14075
[5] 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
[6] Blum, L.; Cucker, F.; Shub, M.; Smale, S., Complexity and real computation, (1998), Springer-Verlag New York
[7] Griffin, Z. A.; Hauenstein, J. D., Real solutions to systems of polynomial equations and parameter continuation, Adv. Geom., 15, 2, 173-187, (2015) · Zbl 1309.65056
[8] Hauenstein, J. D.; Haywood, I.; Liddell, A. C., An a posteriori certification algorithm for Newton homotopies, (ISSAC ’14, (2014), ACM New York), 248-255 · Zbl 1325.65074
[9] Judd, K. L., Numerical methods in economics, (1998), MIT Press Cambride, MA · Zbl 0924.65001
[10] Lee, T.-L.; Li, T.-Y.; Tsai, C.-H., HOM4PS-2.0: a software package for solving polynomial systems by the polyhedral homotopy continuation method, Computing, 83, 109-133, (2008), Software available at · Zbl 1167.65366
[11] Leykin, A., Numerical algebraic geometry for macaulay2, J. Softw. Algebra Geom., 3, 5-10, (2011) · Zbl 1311.14057
[12] Leykin, A.; Sottile, F., Galois groups of Schubert problems via homotopy computation, Math. Comput., 78, 1749-1765, (2009) · Zbl 1210.14064
[13] Metha, D.; Chen, T.; Hauenstein, J. D.; Wales, D. J., Communication: Newton homotopies for sampling stationary points of potential energy landscapes, J. Chem. Phys., 141, 121104, (2014)
[14] Shub, M., Complexity of Bezout’s theorem. VI. geodesics in the condition (number) metric, Found. Comput. Math., 9, 2, 171-178, (2009) · Zbl 1175.65060
[15] Shub, M.; Smale, S., Complexity of Bézout’s theorem. I. geometric aspects, J. Am. Math. Soc., 6, 2, 459-501, (1993) · Zbl 0821.65035
[16] Shub, M.; Smale, S., Complexity of Bezout’s theorem. V. polynomial time, Theor. Comput. Sci., 133, 141-164, (1994) · Zbl 0846.65022
[17] Smale, S., The fundamental theorem of algebra and complexity theory, Bull. Am. Math. Soc. (N. S.), 4, 1, 1-36, (1981) · Zbl 0456.12012
[18] Smale, S., Newton’s method estimates from data at one point, (The Merging of Disciplines: New Directions in Pure, Applied, and Computational Mathematics, Laramie, Wyo., 1985, (1986), Springer New York), 185-196
[19] Sommese, A. J.; Verschelde, J.; Wampler, C. W., Using monodromy to decompose solution sets of polynomial systems into irreducible components, (Applications of Algebraic Geometry to Coding Theory, Physics and Computation, NATO Sci. Ser. II Math. Phys. Chem., vol. 36, (2001), Kluwer Acad. Publ. Dordrecht), 297-315 · Zbl 0990.65051
[20] Verschelde, J., Algorithm 795: phcpack: a general-purpose solver for polynomial systems by homotopy continuation, ACM Trans. Math. Softw., 25, 2, 251-276, (1999), Software available at · 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.