Robust certified numerical homotopy tracking
Carlos Beltran and Anton Leykin
We describe, for the first time, a completely rigorous homotopy (path--following) algorithm (in the Turing machine model) to find approximate zeros of systems of polynomial equations. If the coordinates of the input systems and the initial zero are rational, our algorithm involves only rational computations and if the homotopy is well posed, an approximate zero with integer coordinates of the objective system is obtained. The algorithm generates a (finite) sequence of vectors in $\Z[\ii]^{n+1}$ representing approximate zeros of the polynomial systems following the path. The bit size of the coordinates is polynomial in the logarithm of the maximum of the condition number along the path, and in the size of the input. The total bit complexity is polynomial in the same quantities, and linear in the length of the path in the condition metric.
Paper: to appear in Foundations of Computational Mathematics [arXiv preprint]
Macaulay2 (version 1.4) scripts and examples: