Numerically computing real points on algebraic sets
From MaRDI portal
Abstract: Given a polynomial system f, a fundamental question is to determine if f has real roots. Many algorithms involving the use of infinitesimal deformations have been proposed to answer this question. In this article, we transform an approach of Rouillier, Roy, and Safey El Din, which is based on a classical optimization approach of Seidenberg, to develop a homotopy based approach for computing at least one point on each connected component of a real algebraic set. Examples are presented demonstrating the effectiveness of this parallelizable homotopy based approach.
Infinitesimal deformations are commonly used in real algebraic geometric algorithms. The author uses homotopy continuation to model the deformation, and presents an algorithm for computing a finite set of real roots of a polynomial system containing a point on each connected component. The algorithm computes a finite superset of the isolated roots over the real numbers. Some numerical examples are presented to demonstrate the computational steps of the algorithm.
Recommendations
- Real solving for positive dimensional systems.
- Bertini\_real: software for one- and two-dimensional real algebraic sets
- Computing the real isolated points of an algebraic hypersurface
- scientific article; zbMATH DE number 953044
- Numerical homotopies to compute generic points on positive dimensional algebraic sets
Cites work
- A homotopy for solving general polynomial systems that respects m- homogeneous structures
- A new decision method for elementary algebra
- A numerical local dimension test for points on the solution set of a system of polynomial equations
- A power series method for computing singular solutions to nonlinear analytic systems
- A prolongation-projection algorithm for computing the finite real variety of an ideal
- A transformation to avoid solutions at infinity for polynomial systems
- Adaptive Multiprecision Path Tracking
- Algorithm 921: alphaCertified: certifying solutions to polynomial systems
- Algorithms in real algebraic geometry
- An iterative method converging to a positive solution of certain systems of polynomial equations
- Cell decomposition of almost smooth real algebraic surfaces
- Coefficient-parameter polynomial continuation
- Computing Roadmaps of General Semi-Algebraic Sets
- Computing singular solutions to polynomial systems
- Counting connected components of a semialgebraic set in subexponential time
- Description of the connected components of a semialgebraic set in single exponential time
- Efficient path tracking methods
- Finding all real points of a complex curve
- Finding at least one point in each connected component of a real algebraic set defined by a single equation
- Homotopies for Intersecting Solution Components of Polynomial Systems
- scientific article; zbMATH DE number 5995255 (Why is no real title available?)
- scientific article; zbMATH DE number 1201576 (Why is no real title available?)
- scientific article; zbMATH DE number 1736023 (Why is no real title available?)
- scientific article; zbMATH DE number 953044 (Why is no real title available?)
- Khovanskii-Rolle continuation for real solutions
- Mechanism mobility and a local dimension test
- Numerical decomposition of the solution sets of polynomial systems into irreducible components
- Numerical homotopies to compute generic points on positive dimensional algebraic sets
- On the combinatorial and algebraic complexity of quantifier elimination
- On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals
- On the geometry of polar varieties
- Polar varieties and efficient real elimination
- Polyhedral end games for polynomial continuation
- Real solving for positive dimensional systems.
- Regeneration homotopies for solving systems of polynomials
- Regenerative cascade homotopies for solving polynomial systems
- Semidefinite characterization and computation of zero-dimensional real radical ideals
- Software for numerical algebraic geometry: a paradigm and progress towards its implementation
- Solving systems of polynomial inequalities in subexponential time
- Stepsize control for path tracking
- Symmetric Functions Applied to Decomposing Solution Sets of Polynomial Systems
- The Numerical Solution of Systems of Polynomials Arising in Engineering and Science
- Using monodromy to decompose solution sets of polynomial systems into irreducible components
Cited in
(41)- NC algorithms for real algebraic numbers
- Tensor decomposition and homotopy continuation
- A hybrid procedure for finding real points on a real algebraic set
- Unification and extension of intersection algorithms in numerical algebraic geometry
- Polynomial-time computing over quadratic maps i: sampling in real algebraic sets
- Real solving for positive dimensional systems.
- Homotopy techniques for solving sparse column support determinantal polynomial systems
- Inner-approximating domains of attraction for discrete-time switched systems via multi-step multiple Lyapunov-like functions
- The numerical algebraic geometry of bottlenecks
- Euclidean distance degree and mixed volume
- Smooth points on semi-algebraic sets
- Computing critical points for invariant algebraic systems
- Visualizing planar and space implicit real algebraic curves with singularities
- Defect of Euclidean distance degree
- Solving determinantal systems using homotopy techniques
- Computing real witness points of positive dimensional polynomial systems
- A numerical method for computing border curves of bi-parametric real polynomial systems and applications
- Bertini\_real: software for one- and two-dimensional real algebraic sets
- On computing a cell decomposition of a real surface containing infinitely many singularities
- Finding points on real solution components and applications to differential polynomial systems
- Perturbed homotopies for finding all isolated solutions of polynomial systems
- Validating the completeness of the real solution set of a system of polynomial equations
- Software for the Gale transform of fewnomial systems and a Descartes rule for fewnomials
- Homotopies for connected components of algebraic sets with application to computing critical sets
- scientific article; zbMATH DE number 2086898 (Why is no real title available?)
- Epsilon local rigidity and numerical algebraic geometry
- Critical points via monodromy and local methods
- Sampling and homology via bottlenecks
- A hybrid symbolic-numerical approach to the center-focus problem
- Computing the real isolated points of an algebraic hypersurface
- Finding all real points of a complex curve
- Computing Geometric Feature Sizes for Algebraic Manifolds
- VerifyRealRoots: a Matlab package for computing verified real solutions of polynomials systems of equations and inequalities
- Revealing Bistability in Neurological Disorder Models By Solving Parametric Polynomial Systems Geometrically
- Early Ending in Homotopy Path-Tracking for Real Roots
- Inner-estimating domains of attraction for discrete-time non-polynomial systems with piecewise difference inclusions
- Estimating the minimal domains of attraction of uncertain discrete-time switched systems under state-dependent switching
- Absolute concentration robustness: algebra and geometry
- Applications of singularity theory in applied algebraic geometry and algebraic statistics
- Sampling smooth points on real algebraic sets using perturbations
- Embedding method by real numerical algebraic geometry for structurally unamenable differential-algebraic equations
This page was built for publication: Numerically computing real points on algebraic sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1956231)
