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 |
Keywords:
certified tracking; alpha theory; numerical algebraic geometry; homotopy continuation; Newton’s method; numerical example; polynomial system; Newton corrections; Euler predictorReferences:
| [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: 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: ACM New York), 248-255 · Zbl 1325.65074 |
| [9] | Judd, K. L., Numerical Methods in Economics (1998), MIT Press: 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. The Merging of Disciplines: New Directions in Pure, Applied, and Computational Mathematics, Laramie, Wyo., 1985 (1986), Springer: Springer New York), 185-196 · Zbl 0613.65058 |
| [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. Applications of Algebraic Geometry to Coding Theory, Physics and Computation, NATO Sci. Ser. II Math. Phys. Chem., vol. 36 (2001), Kluwer Acad. Publ.: 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. 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.
