Complexity of sparse polynomial solving: homotopy on toric varieties and the condition metric
For researchers in numerical algebraic geometry, this provides a complexity bound for sparse polynomial solving, though it is an incremental generalization of existing theory.
This paper analyzes the complexity of solving sparse polynomial systems via homotopy continuation on toric varieties, proving that the number of Newton steps is linear in the condition length of the homotopy path. This generalizes a previous result by Shub (2009).
This paper investigates the cost of solving systems of sparse polynomial equations by homotopy continuation. First, a space of systems of $n$-variate polynomial equations is specified through $n$ monomial bases. The natural locus for the roots of those systems is known to be a certain toric variety. This variety is a compactification of $(\mathbb C\setminus\{0\})^n$, dependent on the monomial bases. A toric Newton operator is defined on that toric variety. Smale's alpha theory is generalized to provide criteria of quadratic convergence. Two condition numbers are defined and a higher derivative estimate is obtained in this setting. The Newton operator and related condition numbers turn out to be invariant through a group action related to the momentum map. A homotopy algorithm is given, and is proved to terminate after a number of Newton steps which is linear on the condition length of the lifted homotopy path. This generalizes a result from Shub (2009).