A robust numerical path tracking algorithm for polynomial homotopy continuation
From MaRDI portal
Publication:5146689
DOI10.1137/19M1288036zbMATH Open1457.65023arXiv1909.04984MaRDI QIDQ5146689FDOQ5146689
Authors: Simon Telen, Marc van Barel, J. Verschelde 
Publication date: 26 January 2021
Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)
Abstract: We propose a new algorithm for numerical path tracking in polynomial homotopy continuation. The algorithm is `robust' in the sense that it is designed to prevent path jumping and in many cases, it can be used in (only) double precision arithmetic. It is based on an adaptive stepsize predictor that uses Pad'e techniques to detect local difficulties for function approximation and danger for path jumping. We show the potential of the new path tracking algorithm through several numerical examples and compare with existing implementations.
Full work available at URL: https://arxiv.org/abs/1909.04984
Recommendations
power serieshomotopy continuationpolynomial systemsPadé approximanta priori stepsize controlFabry ratio theorem
Numerical computation of solutions to systems of equations (65H10) Global methods, including homotopy approaches to the numerical solution of nonlinear equations (65H20) Padé approximation (41A21) Numerical computation of roots of polynomial equations (65H04)
Cites Work
- Algorithm 795
- HomotopyContinuation.jl: a package for homotopy continuation in Julia
- The AAA algorithm for rational approximation
- Title not available (Why is that?)
- Condition. The geometry of numerical algorithms
- Numerically solving polynomial systems with Bertini
- Evaluating Derivatives
- Title not available (Why is that?)
- Approximation theory and approximation practice
- The convergence of Padé approximants to functions with branch points
- Title not available (Why is that?)
- Introduction to Numerical Continuation Methods
- Title not available (Why is that?)
- Higher Order Predictors and Adaptive Steplength Control in Path Following Algorithms
- Fast Algorithms for Manipulating Formal Power Series
- Title not available (Why is that?)
- Robust Padé Approximation via SVD
- Numerical decomposition of the solution sets of polynomial systems into irreducible components
- Homotopies Exploiting Newton Polytopes for Solving Sparse Polynomial Systems
- A Polyhedral Method for Solving Sparse Polynomial Systems
- The Numerical Solution of Systems of Polynomials Arising in Engineering and Science
- Title not available (Why is that?)
- Algebraic properties of robust Padé approximants
- Automatic Hessians by reverse accumulation
- Puiseux expansion for space curves
- Robust certified numerical homotopy tracking
- A power series method for computing singular solutions to nonlinear analytic systems
- Computing singular solutions to nonlinear analytic systems
- Adaptive Multiprecision Path Tracking
- Padé approximants and efficient analytic continuation of a power series
- Solving Polynomial Systems Using Continuation for Engineering and Scientific Problems
- Polyhedral end games for polynomial continuation
- ON AN INVERSE PROBLEM FOR THEmTH ROW OF THE PADÉ TABLE
- ON THE CONVERGENCE OF GENERALIZED PADÉ APPROXIMANTS OF MEROMORPHIC FUNCTIONS
- Deformation techniques for sparse systems
- Title not available (Why is that?)
- An algorithm for computing a Padé approximant with minimal degree denominator
- A continuation method based on a high order predictor and an adaptive steplength control
- An Interval Step Control for Continuation Methods
- Sweeping algebraic curves for singular solutions
- Fast and Backward Stable Computation of Roots of Polynomials
- Introduction to numerical algebraic geometry
- Symmetric homotopy construction
- A Neural Network Modeled by an Adaptive Lotka-Volterra System
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the location of poles of Padé approximants
- A stabilized normal form algorithm for generic systems of polynomial equations
- The method of Gauss-Newton to compute power series solutions of polynomial homotopies
- An approach for certifying homotopy continuation paths. Univariate case
- THE POLES OF THEmTH ROW OF THE PADÉ TABLE AND THE SINGULAR POINTS OF A FUNCTION
- The Holomorphic Embedding Loadflow Method for DC Power Systems and Nonlinear DC Circuits
Cited In (21)
- \(u\)-generation: solving systems of polynomials equation-by-equation
- Locating the closest singularity in a polynomial homotopy
- Landau discriminants
- Spherical projective path tracking for homotopy continuation methods
- An approach for certifying homotopy continuation paths. Univariate case
- Polyhedral homotopies in Cox coordinates
- Graceful bases in solution spaces of differential and difference equations
- Contour Integration for Eigenvector Nonlinearities
- Extrapolating solution paths of polynomial homotopies towards singularities with PHCpack and Phcpy
- Efficient path tracking methods
- Multigraded Sylvester forms, duality and elimination matrices
- Algebraic compressed sensing
- GPU accelerated Newton for Taylor series solutions of polynomial homotopies in multiple double precision
- Rigid continuation paths II. structured polynomial systems
- Title not available (Why is that?)
- Mixed precision path tracking for polynomial homotopy continuation
- A novel efficient homotopy continuation method in tracking
- Certified numerical homotopy tracking
- Robust certified numerical homotopy tracking
- Stepsize control for path tracking
- Certified predictor-corrector tracking for Newton homotopies
Uses Software
This page was built for publication: A robust numerical path tracking algorithm for polynomial homotopy continuation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5146689)
