×

Efficient path tracking methods. (English) Zbl 1230.65059

Summary: Path tracking is the fundamental computational tool in homotopy continuation and is therefore key in most algorithms in the emerging field of numerical algebraic geometry. Though the basic notions of predictor-corrector methods have been known for years, there is still much to be considered, particularly in the specialized algebraic setting of solving polynomial systems. In this article, the effects of the choice of predictor method on the performance of a tracker is analyzed, and details for using Runge-Kutta methods in conjunction with adaptive precision are provided. These methods have been implemented in the Bertini software package, and several examples are described.

MSC:

65H20 Global methods, including homotopy approaches to the numerical solution of nonlinear equations
14Q15 Computational aspects of higher-dimensional varieties
65L06 Multistep, Runge-Kutta and extrapolation methods for ordinary differential equations
65H04 Numerical computation of roots of polynomial equations

Software:

Bertini
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Allgower, E.L., Georg, K.: Numerical continuation methods, An introduction. Springer Series in Computational Mathematics, vol. 13. Springer, Berlin (1990) · Zbl 0717.65030
[2] Bates, D.J., Hauenstein, J.D., Sommese, A.J., Wampler, C.W.: Bertini: Software for Numerical Algebraic Geometry. Available at http://www.nd.edu/ommese/bertini · Zbl 1437.14005
[3] Bates, D.J., Hauenstein, J.D., Sommese, A.J., Wampler, C.W.: Adaptive multiprecision path tracking. SIAM J. Numer. Anal., 46, 722–746 (2008) · Zbl 1162.65026 · doi:10.1137/060658862
[4] Bates, D.J., Hauenstein, J.D., Sommese, A.J., Wampler, C.W.: Stepsize control for adaptive multiprecision path tracking. Contemp. Math. 496, 21–31 (2009) · Zbl 1181.65071
[5] Cash, J.R., Karp, A.H.: A variable order Runge-Kutta method for initial value problems with rapidly varying right-hand sides. ACM Trans. Math. Software, 16(3), 201–222 (1990) · Zbl 0900.65234 · doi:10.1145/79505.79507
[6] Enright, W.H., Jackson, K.R., Nørsett, S.P., Thomsen, P.G.: Interpolants for Runge-Kutta formulas. ACM Trans. Math. Software, 12(3), 193–218 (1986) · Zbl 0617.65068 · doi:10.1145/7921.7923
[7] Fehlberg, E.: Klassische Runge-Kutta-Formeln fünfter und siebenter Ordnung mit Schrittweiten-Kontrolle. Computing (Arch. Elektron. Rechnen), 4, 93–106 (1969) · Zbl 0185.41302
[8] Fehlberg, E.: Klassische Runge-Kutta-Formeln vierter und niedrigerer Ordnung mit Schrittweiten-Kontrolle und ihre Anwendung auf Wärmeleitungsprobleme. Computing (Arch. Elektron. Rechnen), 6, 65–71 (1970) · Zbl 0217.53001
[9] Kincaid, D., Cheney, W.: Numerical Analysis: Mathematics of Scientific Computing, 3rd edn. Brooks/Cole Publishing Co., Pacific Grove, CA (2002) · Zbl 0877.65002
[10] Li, T.Y.: Numerical solution of polynomial systems by homotopy continuation methods. In: Cucker, F. (ed.) Handbook of Numerical Analysis, Volume XI, Special Volume: Foundations of Computational Mathematics, North-Holland, pp. 209–304 (2003) · Zbl 1059.65046
[11] Morgan, A.P.: Solving polynomial systems using continuation for engineering and scientific problems. Prentice Hall Inc., Englewood Cliffs, NJ (1987) Reprinted as Classics in Applied Mathematics (2009) 57, SIAM · Zbl 0733.65031
[12] Morgan, A.P., Sommese, A.J.: Computing all solutions to polynomial systems using homotopy continuation. Appl. Math. Comput. 24(2), 115–138 (1987) Errata: Appl. Math. Comput., 51, 209 (1992) · Zbl 0635.65058 · doi:10.1016/0096-3003(87)90064-6
[13] Prince, P.J., Dormand, J.R.: High order embedded Runge-Kutta formulae. J. Comput. Appl. Math. 7(1), 67–75 1981 · Zbl 0449.65048 · doi:10.1016/0771-050X(81)90010-3
[14] Shampine, L.F.: Numerical Solution of Ordinary Differential Equations. Chapman & Hall, New York (1994) · Zbl 0832.65063
[15] Sommese, A.J., Wampler, C.W.: The Numerical Solution of Systems of Polynomials Arising in Engineering and Science. World Scientific, Singapore (2005) · Zbl 1091.65049
[16] Verner, J.H.: Explicit Runge-Kutta methods with estimates of the local truncation error. SIAM J. Numer. Anal. 15(4), 772–790 (1978) · Zbl 0403.65029 · doi:10.1137/0715051
[17] Wampler, C.W., Morgan, A., Sommese, A.J.: Complete solution of the nine-point path synthesis problem for four-bar linkages. ASME J. Mech. Des. 114(1), 153–159 (1992) · doi:10.1115/1.2916909
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.