A Polyhedral Method for Solving Sparse Polynomial Systems

DOI10.2307/2153370zbMath0849.65030OpenAlexW1989923040MaRDI QIDQ4878511

Bernd Sturmfels, Birkett Huber

Publication date: 11 November 1996

Full work available at URL: https://doi.org/10.2307/2153370

zbMATH Keywords

algorithmNewton polytopehomotopy methodnumerical continuation methodisolated rootssparse polynomial system

Mathematics Subject Classification ID

Numerical computation of solutions to systems of equations (65H10) Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral) (30C15)

Related Items (only showing first 100 items - show all)

Finiteness of relative equilibria of the four-body problem ⋮ Computing all nonsingular solutions of cyclic-\(n\) polynomial using polyhedral homotopy continuation methods ⋮ Polymake.jl: A New Interface to polymake ⋮ 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 ⋮ Mixed multiplicities of ideals versus mixed volumes of polytopes ⋮ Estimating the Attraction Domain for the Boost Inverter ⋮ Finding all Nash equilibria of a finite game using polynomial algebra ⋮ A global view of residues in the torus ⋮ 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 ⋮ Cell decomposition of almost smooth real algebraic surfaces ⋮ Counting Equilibria of the Kuramoto Model Using Birationally Invariant Intersection Index ⋮ Polynomial equation solving by lifting procedures for ramified fibers ⋮ High probability analysis of the condition number of sparse polynomial systems ⋮ Numerical root finding via Cox rings ⋮ Mixed-volume computation by dynamic lifting applied to polynomial system solving ⋮ Upper and lower bounds for Grigoriev's algorithm for solving integral tropical linear systems ⋮ Toric eigenvalue methods for solving sparse polynomial systems ⋮ Nine equilibrium points of four point charges on the plane ⋮ Computing mixed volume and all mixed cells in quermassintegral time ⋮ The Maximum Likelihood Degree of Sparse Polynomial Systems ⋮ Numerical homotopies from Khovanskii bases ⋮ A polyhedral homotopy algorithm for real zeros ⋮ The Tropical Nullstellensatz and Positivstellensatz for Sparse Polynomial Systems ⋮ Contour Integration for Eigenvector Nonlinearities ⋮ Unmixing the mixed volume computation ⋮ Rational points of lattice ideals on a toric variety and toric codes ⋮ The Canny-Emiris conjecture for the sparse resultant ⋮ Computing isolated roots of sparse polynomial systems in affine space ⋮ Computational approach to compact Riemann surfaces ⋮ Tropical combinatorial Nullstellensatz and sparse polynomials ⋮ Facets and facet subgraphs of symmetric edge polytopes ⋮ Heuristic methods for computing the minimal multi-homogeneous Bézout number. ⋮ Minimizing multi-homogeneous Bézout numbers by a local search method ⋮ Regenerative cascade homotopies for solving polynomial systems ⋮ Decoupled molecules with binding polynomials of bidegree \((n,2)\) ⋮ Counting and locating the solutions of polynomial systems of maximum likelihood equations. I. ⋮ On the frontiers of polynomial computations in tropical geometry ⋮ Stabilization of monomial maps in higher codimension ⋮ A Robust Numerical Path Tracking Algorithm for Polynomial Homotopy Continuation ⋮ Unification and extension of intersection algorithms in numerical algebraic geometry ⋮ Homotopy techniques for solving sparse column support determinantal polynomial systems ⋮ Bernstein's theorem in affine space ⋮ Maslov dequantization and the homotopy method for solving systems of nonlinear algebraic equations ⋮ Tropical effective primary and dual Nullstellensätze ⋮ Foreword. What is numerical algebraic geometry? ⋮ Mixed cell computation in HOM4ps ⋮ Parallel degree computation for binomial systems ⋮ Certifying solutions to square systems of polynomial-exponential equations ⋮ Mixed volume computation in parallel ⋮ Beyond polyhedral homotopies ⋮ Elimination for generic sparse polynomial systems ⋮ A systematic framework for solving geometric constraints analytically ⋮ 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 ⋮ Parameter estimation in linear models with heteroscedastic variances subject to order restrictions ⋮ 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 ⋮ Well-Posedness in Unconstrained Polynomial Optimization Problems ⋮ Seven mutually touching infinite cylinders ⋮ Single-lifting Macaulay-type formulae of generalized unmixed sparse resultants ⋮ Fibre tilings ⋮ Bernstein's second theorem and Viro's method for sparse polynomial systems in chemistry ⋮ Macaulay style formulas for sparse resultants ⋮ Algebraic \(\mathbb C^*\)-actions and the inverse kinematics of a general 6R manipulator ⋮ Polynomial Homotopy Method for the Sparse Interpolation Problem Part I: Equally Spaced Sampling ⋮ Linear homotopy method for computing generalized tensor eigenpairs ⋮ A constrained homotopy technique for excluding unwanted solutions from polynomial equations arising in kinematics problems ⋮ Solving Polynomial Systems via Truncated Normal Forms ⋮ Computing Tensor Eigenvalues via Homotopy Methods ⋮ Clustering complex zeros of triangular systems of polynomials ⋮ HOM4PS-2.0: a software package for solving polynomial systems by the polyhedral homotopy continuation method ⋮ Lattice polytopes cut out by root systems and the Koszul property ⋮ Random polynomials with prescribed Newton polytope ⋮ Regeneration homotopies for solving systems of polynomials ⋮ Solving decomposable sparse systems ⋮ Matrices in elimination theory ⋮ Finding all isolated zeros of polynomial systems in \(\mathbb{C}^n\) via stable mixed volumes ⋮ A polynomial-time algorithm to approximate the mixed volume within a simply exponential factor ⋮ Exploiting Chordal Structure in Polynomial Ideals: A Gröbner Bases Approach ⋮ 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 ⋮ Mixed volume techniques for embeddings of Laman graphs ⋮ Central configurations of the five-body problem with equal masses ⋮ How to count efficiently all affine roots of a polynomial system ⋮ Directed acyclic decomposition of Kuramoto equations ⋮ A sparse effective Nullstellensatz ⋮ State polytopes related to two classes of combinatorial neural codes ⋮ Toric intersection theory for affine root counting ⋮ Criteria for strict monotonicity of the mixed volume of convex polytopes ⋮ Euclidean distance degree and mixed volume ⋮ Valuations and Tensor Weights on Polytopes ⋮ A family of sparse polynomial systems arising in chemical reaction systems ⋮ Epsilon local rigidity and numerical algebraic geometry ⋮ Early Ending in Homotopy Path-Tracking for Real Roots

Cites Work

• A homotopy for solving general polynomial systems that respects m- homogeneous structures
• Chow polytopes and general resultants
• Fiber polytopes
• Mixed volumes of polytopes
• On the Newton polytope of the resultant
• Product formulas for resultants and Chow forms
• Introduction to Toric Varieties. (AM-131)
• Homotopies Exploiting Newton Polytopes for Solving Sparse Polynomial Systems
• On The Complexity of Computing Mixed Volumes
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A Polyhedral Method for Solving Sparse Polynomial Systems