A baby step-giant step roadmap algorithm for general algebraic sets

DOI10.1007/s10208-014-9212-1zbMath1322.14090arXiv1201.6439OpenAlexW2118254039MaRDI QIDQ486687

Saugata Basu, Marie-Françoise Roy, Mohab Safey El Din, Éric Schost

Publication date: 16 January 2015

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

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

zbMATH Keywords

complexityreal algebraic setcritical pointsinfinitesimal deformationbaby step-giant steproadmap

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Real algebraic sets (14P05) Effectivity, complexity and computational aspects of algebraic geometry (14Q20)

Related Items

A Geometric Approach for Analyzing Parametric Biological Systems by Exploiting Block Triangular Structure, Numerical roadmap of smooth bounded real algebraic surface, Positive dimensional parametric polynomial systems, connectivity queries and applications in robotics, Algorithm for Connectivity Queries on Real Algebraic Curves, Persistent Homology of Semialgebraic Sets, Computing roadmaps in unbounded smooth real algebraic sets. I: Connectivity results, Topology of real multi-affine hypersurfaces and a homological stability property, Divide and conquer roadmap for algebraic sets, Solving determinantal systems using homotopy techniques, Homotopy techniques for solving sparse column support determinantal polynomial systems, A Numerical Method for Computing Border Curves of Bi-parametric Real Polynomial Systems and Applications, Bit complexity for computing one point in each connected component of a smooth real algebraic set, Computing critical points for invariant algebraic systems, On the Central Path of Semidefinite Optimization: Degree and Worst-Case Convergence Rate, Computing real witness points of positive dimensional polynomial systems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A baby steps/giant steps probabilistic algorithm for computing roadmaps in smooth bounded real hypersurface
• On the Piano Movers problem. II: General techniques for computing topological properties of real algebraic manifolds
• Counting connected components of a semialgebraic set in subexponential time
• Construction of roadmaps in semi-algebraic sets
• Computing roadmaps of semi-algebraic sets on a variety
• Algorithms in real algebraic geometry
• Dynamical method in algebra: Effective Nullstellensätze