Certified Numerical Homotopy Tracking

Abstract

Given a homotopy connecting two polynomial systems, we provide a rigorous algorithm for tracking a regular homotopy path connecting an approximate zero of the start system to an approximate zero of the target system. Our method uses recent results on the complexity of homotopy continuation rooted in the alpha theory of Smale. Experimental results obtained with an implementation in the numerical algebraic geometry package Macaulay2 demonstrate the practicality of the algorithm. In particular, we confirm the theoretical results for random linear homotopies and illustrate the plausibility of a conjecture by Shub and Smale on a good initial pair.

2000 AMS Subject Classification:

• 14Q20
• 65H10
• 65H20

Keywords:

• Computational aspects of algebraic geometry
• systems of equations
• continual methods
• homotopy methods
• approximate zero
• certified algorithms
• complexity

Acknowledgments

The authors would like to thank Mike Shub for insightful comments. The second author is grateful to Jan Verschelde for early discussions of practical certification issues. This work was partially done while the authors were attending a workshop on the complexity of numerical computation as part of the FoCM thematic program hosted by the Fields Institute, Toronto. We thank that institution for their kind support. We are also thankful to the referees for their helpful comments.

Carlos Beltrán's research was partially supported by MTM2007-62799 and MTM2010-16051, Spanish Ministry of Science (MICINN). Anton Leykin's research was partially supported by NSF grant DMS-0914802.

Notes

¹The original pair suggested by Shub and Smale had no d ^1/2 _i factors like those here. As has been done in other papers by several authors, we add these factors here to optimize the condition number μ(g, e ₀).