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

DOI10.1093/IMANUM/DRS007zbMATH Open1266.65080arXiv1104.2084OpenAlexW1763512893MaRDI QIDQ4907959FDOQ4907959

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)

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.

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

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

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)

Cited In (14)

• Complexity of sparse polynomial solving: homotopy on toric varieties and the condition metric
• Smale's fundamental theorem of algebra reconsidered
• 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
• 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
• Complexity of an Homotopy Method at the Neighbourhood of a Zero
• 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
• 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)