Adaptive step-size selection for homotopy methods to solve polynomial equations

DOI10.1093/IMANUM/DRS007MaRDI QIDQ4907959zbMATH OpenOpenAlexFDO

Authors Gregorio Malajovich, Michael Shub, Jean-Pierre Dedieu

Publication date 27 February 2013

Published in IMA Journal of Numerical Analysis (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1104.2084

zbMATH Keywords

condition metrichomotopy methodapproximate zero

Mathematics Subject Classification ID

Numerical computation of solutions to systems of equations (65H10) Global methods, including homotopy approaches to the numerical solution of nonlinear equations (65H20)

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.

Recommendations

• A continuation method to solve polynomial systems and its complexity
• Homotopy continuation method for solving systems of nonlinear and polynomial equations
• Numerically determining solutions of systems of polynomial equations
• scientific article; zbMATH DE number 1069614
• On the solutions to polynomial systems obtained by homotopy methods

Cited in

(15)

• Smale's fundamental theorem of algebra reconsidered
• Complexity of sparse polynomial solving: homotopy on toric varieties and the condition metric
• A continuation method to solve polynomial systems and its complexity
• Spherical Radon transform and the average of the condition number on certain Schubert subvarieties of a Grassmannian
• Complexity of an homotopy method at the neighbourhood of a zero
• Polyhedral homotopies in Cox coordinates
• Fast linear homotopy to find approximate zeros of polynomial systems
• Complexity of path-following methods for the eigenvalue problem
• On the geometry and topology of the solution variety for polynomial system solving
• Rigid continuation paths I. Quasilinear average complexity for solving polynomial systems
• Condition length and complexity for the solution of polynomial systems
• Adaptive strategies for solving parameterized systems using homotopy continuation
• An a posteriori certification algorithm for Newton homotopies
• Robust certified numerical homotopy tracking
• Stepsize control for path tracking

This page was built for publication: Adaptive step-size selection for homotopy methods to solve polynomial equations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4907959)