Computing real witness points of positive dimensional polynomial systems

DOI10.1016/j.tcs.2017.03.035zbMath1390.14188OpenAlexW2564591273MaRDI QIDQ2357373

Greg Reid, Wenyuan Wu, Yong Feng

Publication date: 13 June 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2017.03.035

zbMATH Keywords

homotopy continuationnumerical algebraic geometryreal algebraic geometrysingular critical pointsreal witness points

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Real algebraic sets (14P05) Global methods, including homotopy approaches to the numerical solution of nonlinear equations (65H20) Real polynomials: location of zeros (26C10) Effectivity, complexity and computational aspects of algebraic geometry (14Q20) Real algebra (13J30)

Related Items

A Geometric Approach for Analyzing Parametric Biological Systems by Exploiting Block Triangular Structure, Numerical roadmap of smooth bounded real algebraic surface, Nine equilibrium points of four point charges on the plane, Revealing Bistability in Neurological Disorder Models By Solving Parametric Polynomial Systems Geometrically, Inner-estimating domains of attraction for discrete-time non-polynomial systems with piecewise difference inclusions, Visualizing planar and space implicit real algebraic curves with singularities, Inner-approximating domains of attraction for discrete-time switched systems via multi-step multiple Lyapunov-like functions

Uses Software

• RAGlib
• Bertini

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A baby step-giant step roadmap algorithm for general algebraic sets
• A baby steps/giant steps probabilistic algorithm for computing roadmaps in smooth bounded real hypersurface
• Properness defects and projections and computation of at least one point in each connected component of a real algebraic set
• A prolongation-projection algorithm for computing the finite real variety of an ideal
• Real quantifier elimination is doubly exponential
• Counting connected components of a semialgebraic set in subexponential time
• Polar varieties, real equation solving, and data structures: the hypersurface case
• Estimations for the separation number of a polynomial system
• Robust certified numerical homotopy tracking
• Numerically computing real points on algebraic sets
• Cell decomposition of almost smooth real algebraic surfaces
• Numerical solutions of index-1 differential algebraic equations can be computed in polynomial time
• A new decision method for elementary algebra
• Point searching in real singularcomplete intersection varieties: algorithms of intrinsic complexity
• Computing cylindrical algebraic decomposition via triangular decomposition
• The DMM bound
• Finding points on real solution components and applications to differential polynomial systems
• Verified error bounds for real solutions of positive-dimensional polynomial systems
• The Cheater’s Homotopy: An Efficient Procedure for Solving Systems of Polynomial Equations
• A Nearly Optimal Algorithm for Deciding Connectivity Queries in Smooth and Bounded Real Algebraic Sets
• Computing real solutions of polynomial systems via low-rank moment matrix completion
• On the Minimum of a Polynomial Function on a Basic Closed Semialgebraic Set and Applications
• The Numerical Solution of Systems of Polynomials Arising in Engineering and Science
• Triangular decomposition of semi-algebraic systems
• Algorithms in real algebraic geometry
• Finding at least one point in each connected component of a real algebraic set defined by a single equation