Khovanskii-Rolle continuation for real solutions

DOI10.1007/S10208-011-9097-1zbMATH Open1231.14047arXiv0908.4579OpenAlexW2127578193MaRDI QIDQ660674FDOQ660674

Frank Sottile, Daniel J. Bates

Publication date: 4 February 2012

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

Abstract: We present a new continuation algorithm to find all nondegenerate real solutions to a system of polynomial equations. Unlike homotopy methods, it is not based on a deformation of the system; instead, it traces real curves connecting the solutions of one system of equations to those of another, eventually leading to the desired real solutions. It also differs from homotopy methods in that it follows only real paths and computes no complex solutions of the original equations. The number of curves traced is bounded by the fewnomial bound for real solutions, and the method takes advantage of any slack in that bound.

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

Recommendations

• A special homotopy continuation method for a class of polynomial systems
• Homotopy continuation method for solving systems of nonlinear and polynomial equations
• Publication:3477888
• A polyhedral homotopy algorithm for real zeros
• Solving polynomial systems by polyhedral homotopies

zbMATH Keywords

continuationhomotopyreal algebraic geometrypolynomial systemfewnomialnumerical algebraic geometryGale dualKhovanskii-Rolle

Mathematics Subject Classification ID

Numerical computation of solutions to systems of equations (65H10) Real algebraic sets (14P05) Computational aspects in algebraic geometry (14Q99) Global methods, including homotopy approaches to the numerical solution of nonlinear equations (65H20)

Cites Work

• HOM4PS-2.0: a software package for solving polynomial systems by the polyhedral homotopy continuation method
• Algorithm 795
• Lectures on Polytopes
• Introduction to Numerical Continuation Methods
• Solving zero-dimensional systems through the rational univariate representation
• Semidefinite characterization and computation of zero-dimensional real radical ideals
• The Numerical Solution of Systems of Polynomials Arising in Engineering and Science
• Title not available (Why is that?)
• Improving the efficiency of exclusion algorithms
• Bounds on the Number of Real Solutions to Polynomial Equations
• Khovanskii-Rolle continuation for real solutions
• Gale duality for complete intersections
• Adaptive Multiprecision Path Tracking
• Solving Polynomial Systems Using Continuation for Engineering and Scientific Problems
• Polyhedral end games for polynomial continuation
• Bertini_real: Software for One- and Two-Dimensional Real Algebraic Sets
• Subdivision methods for solving polynomial equations
• Title not available (Why is that?)
• On the complexity of exclusion algorithms for optimization

Cited In (13)

• Univariate Real Root Isolation over a Single Logarithmic Extension of Real Algebraic Numbers
• Numerical homotopies to compute generic points on positive dimensional algebraic sets
• A hybrid procedure for finding real points on a real algebraic set
• Spherical Radon transform and the average of the condition number on certain Schubert subvarieties of a Grassmannian
• Determinantal representations of hyperbolic curves via polynomial homotopy continuation
• Software for the Gale transform of fewnomial systems and a Descartes rule for fewnomials
• Khovanskii-Rolle continuation for real solutions
• Gale duality for complete intersections
• Numerically computing real points on algebraic sets
• A polyhedral homotopy algorithm for real zeros
• The numerical algebraic geometry of bottlenecks
• Early Ending in Homotopy Path-Tracking for Real Roots
• The Approach of Moments for Polynomial Equations

Uses Software

• HOM4PS
• PHCpack
• SINGULAR
• Bertini
• ISOLATE

This page was built for publication: Khovanskii-Rolle continuation for real solutions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q660674)