Complexity of sparse polynomial solving: homotopy on toric varieties and the condition metric
arXiv:1606.03410 · doi:10.1007/s10208-007-9017-6
Abstract
This paper investigates the cost of solving systems of sparse polynomial equations by homotopy continuation. First, a space of systems of -variate polynomial equations is specified through 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 , 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).
arXiv comment3 figures, 44 pages
References in corpus (8)
- Newton Method on Riemannian Manifolds: Covariant Alpha-Theory
- Complexity of sparse polynomial solving: homotopy on toric varieties and the condition metric
- High Probability Analysis of the Condition Number of Sparse Polynomial Systems
- Adaptative Step Size Selection for Homotopy Methods to Solve Polynomial Equations
- Convexity properties of the condition number
- Tropical Homotopy Continuation
- On the expected number of zeros of nonlinear equations
- Condition metrics in the three classical spaces
Cited by in corpus (15)
- Complexity of sparse polynomial solving: homotopy on toric varieties and the condition metric
- Adaptative Step Size Selection for Homotopy Methods to Solve Polynomial Equations
- A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time
- Convexity properties of the condition number
- A Numerical Algorithm for Zero Counting. III: Randomization and Condition
- A stable, polynomial-time algorithm for the eigenpair problem
- Complexity of Sparse Polynomial Solving 2: Renormalization
- On a Problem Posed by Steve Smale
- Smale's Fundamental Theorem of Algebra reconsidered
- Average polynomial time for eigenvector computations
- Geometry of Polynomials and Root-Finding via Path-Lifting
- Robust certified numerical homotopy tracking
- Fast Computation of Zeros of Polynomial Systems with Bounded Degree under Finite-precision
- Condition length and complexity for the solution of polynomial systems
- Rigid continuation paths II. Structured polynomial systems