A Nearly Optimal Algorithm for Deciding Connectivity Queries in Smooth and Bounded Real Algebraic Sets
From MaRDI portal
Publication:3177875
DOI10.1145/2996450zbMath1426.68311arXiv1307.7836OpenAlexW2279788372MaRDI QIDQ3177875
Éric Schost, Mohab Safey El Din
Publication date: 2 August 2018
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1307.7836
complexityalgorithmssymbolic computationreal algebraic geometryconnectivity queriesnonlinear computational geometry
Symbolic computation and algebraic computation (68W30) Real algebraic sets (14P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Related Items
Gröbner bases and critical values: the asymptotic combinatorics of determinantal systems ⋮ Real root finding for low rank linear matrices ⋮ Solving rank-constrained semidefinite programs in exact arithmetic ⋮ 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 ⋮ Fast Algorithms for Discrete Differential Equations ⋮ Algorithm for Connectivity Queries on Real Algebraic Curves ⋮ Improved complexity bounds for counting points on hyperelliptic curves ⋮ Refined F5 Algorithms for Ideals of Minors of Square Matrices ⋮ Bit complexity for multi-homogeneous polynomial system solving -- application to polynomial minimization ⋮ Real root finding for determinants of linear matrices ⋮ Computing roadmaps in unbounded smooth real algebraic sets. I: Connectivity results ⋮ Computing real radicals and \(S\)-radicals of polynomial systems ⋮ Symmetric matrices whose entries are linear functions ⋮ Solving determinantal systems using homotopy techniques ⋮ Exact algorithms for semidefinite programs with degenerate feasible set ⋮ Homotopy techniques for solving sparse column support determinantal polynomial systems ⋮ Foreword ⋮ A Note on Polynomial Solvability of the CDT Problem ⋮ On exact Reznick, Hilbert-Artin and Putinar's representations ⋮ On types of degenerate critical points of real polynomial functions ⋮ Counting points on hyperelliptic curves with explicit real multiplication in arbitrary genus ⋮ Exact Algorithms for Linear Matrix Inequalities ⋮ Bit complexity for computing one point in each connected component of a smooth real algebraic set ⋮ Computing critical points for invariant algebraic systems ⋮ Solving parametric systems of polynomial equations over the reals through Hermite matrices ⋮ Computing real witness points of positive dimensional polynomial systems
