Polyhedral end games for polynomial continuation
Homotopy continuation methods have been extensively applied for over 20 years to numerically compute all of the solutions of polynomial systems in \(\mathbb{C}^n\). One key problem with this method is that often many homotopy paths lead to solutions at infinity. In such a case, the issue arises of deciding whether a path is diverging or merely converging to a solution with large components. Moreover, solutions at infinity are often also singular, which makes it difficult to determine whether a solution corresponding to a path really lies at infinity. The polyhedral homotopy method based upon Bernshtein's mixed volume bound generically has an exact number of paths for the finite solutions. However, many practical problems are not generic and as a result, homotopy methods based upon the mixed volume bound may still require the tracing of some divergent paths. The present paper deals with determining whether a path is diverging. Algorithms have been given by the authors and their co-authors for producing a start system \(G\) with a complete set of solutions \({\mathbf z}_i \in \mathbb{C}^n-{\mathbf 0}\), so that the homotopy equation \[ H({\mathbf x},t):=(1-t)G({\mathbf x})+tF({\mathbf x})={\mathbf 0} \] gives nonsingular curves \({\mathbf x}_i(t)\) such that \({\mathbf x}_i(0)={\mathbf z}_i\), and all solutions of \(F({\mathbf x})={\mathbf 0}\) are among the limit points \(\lim_{t\to 1}{\mathbf x}_i(t)\). The deficient case occurs when \(F({\mathbf x})={\mathbf 0}\) fails to have the full number of solutions as \(G({\mathbf x})={\mathbf 0}\) has. The technique for determining whether a path is diverging is based upon a proof of Bernshtein's discriminant condition: solution paths which leave \(\mathbb{C}^n-{\mathbf 0}\) correspond to solutions in some face system. A technique is given for numerically estimating an outer normal to the face which causes the deficiency. Identifying the deficient face can lead to the development of better performing homotopies. A further contribution of the paper is an extrapolation method for estimating the cycle number of a path. This number plays an important role in the end game strategies used in several homotopy algorithms.
- scientific article; zbMATH DE number 3062460
- Polynomial games and determinacy
- Polymatrix games and optimization problems
- A note on polymatrix games
- scientific article; zbMATH DE number 4179164
- A polymatroid associated with convex games
- scientific article; zbMATH DE number 988830
- Publication:3468723
- Characterizing the value functions of polynomial games
- Polytopes and the existence of approximate equilibria in discontinuous games
- HOM4PS-2.0: a software package for solving polynomial systems by the polyhedral homotopy continuation method
- Toric intersection theory for affine root counting
- Toric Newton method for polynomial homotopies
- A family of sparse polynomial systems arising in chemical reaction systems
- Unification and extension of intersection algorithms in numerical algebraic geometry
- Bernstein's second theorem and Viro's method for sparse polynomial systems in chemistry
- Solving polynomial systems by polyhedral homotopies
- Computing all nonsingular solutions of cyclic-n polynomial using polyhedral homotopy continuation methods
- Numerically computing real points on algebraic sets
- Solving decomposable sparse systems
- Locating the closest singularity in a polynomial homotopy
- Numerical root finding via Cox rings
- Multiprojective witness sets and a trace test
- An adaptive homotopy method for computing bifurcations of nonlinear parametric systems
- PHoMpara-parallel implementation of the polyhedral homotopy continuation method for polynomial systems
- Numerical Evidence for a Conjecture in Real Algebraic Geometry
- Polynomial homotopy method for the sparse interpolation problem. I: Equally spaced sampling
- Computing Tropical Curves via Homotopy Continuation
- Computing all space curve solutions of polynomial systems by polyhedral methods
- Isosingular sets and deflation
- Note on the end game in homotopy zero curve tracking
- Robust continuation methods for tracing solution curves of parameterized systems
- Newton polytopes and witness sets
- Foreword. What is numerical algebraic geometry?
- A robust numerical path tracking algorithm for polynomial homotopy continuation
- scientific article; zbMATH DE number 6296052 (Why is no real title available?)
- Balancing the lifting values to improve the numerical stability of polyhedral homotopy continuation methods
- Early Ending in Homotopy Path-Tracking for Real Roots
- Polyhedral homotopies in Cox coordinates
- Khovanskii-Rolle continuation for real solutions
- Branch points of homotopies: distribution and probability of failure
- Sweeping algebraic curves for singular solutions
This page was built for publication: Polyhedral end games for polynomial continuation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1272646)
