Homotopies Exploiting Newton Polytopes for Solving Sparse Polynomial Systems

DOI10.1137/0731049zbMath0809.65048OpenAlexW2034955763WikidataQ57779002 ScholiaQ57779002MaRDI QIDQ4305440

Pierre Verlinden, Jan Verschelde, Ronald Cools

Publication date: 13 October 1994

Published in: SIAM Journal on Numerical Analysis (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0731049

zbMATH Keywords

number of solutions mixed volume polynomial system Newton polytopes homotopy continuation method Bernstein-Kushnirenko-Khovanskij upper bound

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)

Related Items (62)

Computing all nonsingular solutions of cyclic-$n$ polynomial using polyhedral homotopy continuation methods ⋮ A convex geometric approach to counting the roots of a polynomial system ⋮ Homotopies for solving polynomial systems within a bounded domain ⋮ Perturbed homotopies for finding all isolated solutions of polynomial systems ⋮ Imperialist competitive algorithm for solving systems of nonlinear equations ⋮ Real enumerative geometry and effective algebraic equivalence ⋮ Numeric vs. symbolic homotopy algorithms in polynomial system solving: a case study ⋮ Generating approximate parametric roots of parametric polynomials ⋮ PHoMpara-parallel implementation of the polyhedral homotopy continuation method for polynomial systems ⋮ Chaotic quantum behaved particle swarm optimization algorithm for solving nonlinear system of equations ⋮ Parametric estimation of affine deformations of planar shapes ⋮ High probability analysis of the condition number of sparse polynomial systems ⋮ Deformation techniques to solve generalised Pham systems ⋮ Numerical root finding via Cox rings ⋮ Mixed-volume computation by dynamic lifting applied to polynomial system solving ⋮ Toric eigenvalue methods for solving sparse polynomial systems ⋮ \textit{Helios}: A modeling language for global optimization and its implementation in \textit{Newton} ⋮ The Maximum Likelihood Degree of Sparse Polynomial Systems ⋮ Numerical homotopies from Khovanskii bases ⋮ Unmixing the mixed volume computation ⋮ Computing isolated roots of sparse polynomial systems in affine space ⋮ Early Ending in Homotopy Path-Tracking for Real Roots ⋮ A Fast Algorithm for Computing Macaulay Null Spaces of Bivariate Polynomial Systems ⋮ Polyhedral homotopies in Cox coordinates ⋮ Minimizing multi-homogeneous Bézout numbers by a local search method ⋮ On the general boundary element method ⋮ Algorithms for computing Nash equilibria in deterministic LQ games ⋮ Linear programming system identification: the general nonnegative parameters case ⋮ Solving determinantal systems using homotopy techniques ⋮ A Robust Numerical Path Tracking Algorithm for Polynomial Homotopy Continuation ⋮ Unification and extension of intersection algorithms in numerical algebraic geometry ⋮ Bernstein's theorem in affine space ⋮ On the use of predictor-corrector continuation to trace implicitly defined curves and calculating bifurcation ⋮ Foreword. What is numerical algebraic geometry? ⋮ A new hybrid algorithm based on chaotic maps for solving systems of nonlinear equations ⋮ Numerical Evidence for a Conjecture in Real Algebraic Geometry ⋮ A scaling algorithm for polynomial constraint satisfaction problems ⋮ Elimination for generic sparse polynomial systems ⋮ Optimization problem in multi-homogeneous homotopy method ⋮ A symmetric homotopy and hybrid polynomial system solving method for mixed trigonometric polynomial systems ⋮ Balancing the lifting values to improve the numerical stability of polyhedral homotopy continuation methods ⋮ Relations between roots and coefficients, interpolation and application to system solving ⋮ Tropical algebraic geometry in Maple: a preprocessing algorithm for finding common factors for multivariate polynomials with approximate coefficients ⋮ Linear programming system identification ⋮ Algebraic $\mathbb C^*$-actions and the inverse kinematics of a general 6R manipulator ⋮ Computation of the distance to semi-algebraic sets ⋮ Polynomial Homotopy Method for the Sparse Interpolation Problem Part I: Equally Spaced Sampling ⋮ Exact line and plane search for tensor optimization ⋮ Applying genetic algorithms for solving nonlinear algebraic equations ⋮ Computing Tropical Curves via Homotopy Continuation ⋮ A Polyhedral Method for Solving Sparse Polynomial Systems ⋮ Regeneration homotopies for solving systems of polynomials ⋮ Matrices in elimination theory ⋮ The BKK root count in $\mathbf {C}^n$ ⋮ Computing All Space Curve Solutions of Polynomial Systems by Polyhedral Methods ⋮ Deformation techniques for sparse systems ⋮ Toric Newton method for polynomial homotopies ⋮ A numerical algorithm to find soft-constrained Nash equilibria in scalar LQ-games ⋮ How to count efficiently all affine roots of a polynomial system ⋮ A sparse effective Nullstellensatz ⋮ A Complete Implementation for Computing General Dimensional Convex Hulls ⋮ Solving sparse non-negative tensor equations: algorithms and applications

This page was built for publication: Homotopies Exploiting Newton Polytopes for Solving Sparse Polynomial Systems