Adaptative Step Size Selection for Homotopy Methods to Solve Polynomial Equations

Abstract

Given a C^1 path of systems of homogeneous polynomial equations f_t, t in [a,b] and an approximation x_a to a zero zeta_a of the initial system f_a, we show how to adaptively choose the step size for a Newton based homotopy method so that we approximate the lifted path (f_t,zeta_t) in the space of (problems, solutions) pairs. The total number of Newton iterations is bounded in terms of the length of the lifted path in the condition metric.

References in corpus (1)

• Complexity of sparse polynomial solving: homotopy on toric varieties and the condition metric

Cited by in corpus (9)

• Complexity of sparse polynomial solving: homotopy on toric varieties and the condition metric
• A stable, polynomial-time algorithm for the eigenpair problem
• Complexity of Sparse Polynomial Solving 2: Renormalization
• Average polynomial time for eigenvector computations
• Rigid continuation paths I. Quasilinear average complexity for solving polynomial systems
• Smale's Fundamental Theorem of Algebra reconsidered
• Complexity of Path-Following Methods for the Eigenvalue Problem
• Robust certified numerical homotopy tracking
• Condition length and complexity for the solution of polynomial systems