146
Views
20
CrossRef citations to date
0
Altmetric
Original Articles

Certified Numerical Homotopy Tracking

&
Pages 69-83 | Received 20 Dec 2010, Accepted 21 Jun 2011, Published online: 13 Mar 2012
 

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:

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

1The 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 0).

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.