Algorithms in real algebraic geometry: a survey
From MaRDI portal
Publication:4604289
zbMATH Open1398.14062arXiv1409.1534MaRDI QIDQ4604289FDOQ4604289
Authors: Saugata Basu 
Publication date: 23 February 2018
Abstract: We survey both old and new developments in the theory of algorithms in real algebraic geometry -- starting from effective quantifier elimination in the first order theory of reals due to Tarski and Seidenberg, to more recent algorithms for computing topological invariants of semi-algebraic sets. We emphasize throughout the complexity aspects of these algorithms and also discuss the computational hardness of the underlying problems. We also describe some recent results linking the computational hardness of decision problems in the first order theory of the reals, with that of computing certain topological invariants of semi-algebraic sets. Even though we mostly concentrate on exact algorithms, we also discuss some numerical approaches involving semi-definite programming that have gained popularity in recent times.
Full work available at URL: https://arxiv.org/abs/1409.1534
Recommendations
Symbolic computation and algebraic computation (68W30) Topology of real algebraic varieties (14P25) Semialgebraic sets and related spaces (14P10) Computational aspects of higher-dimensional varieties (14Q15)
Cited In (26)
- Title not available (Why is that?)
- Some aspects of complexity in real algebraic geometry
- Algorithms in real algebraic geometry
- Algorithms in real algebraic geometry
- Title not available (Why is that?)
- Grid methods in computational real algebraic (and semialgebraic) geometry
- Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications
- On the Theoretical and Practical Complexity of the Existential Theory of Reals
- Title not available (Why is that?)
- On the central path of semidefinite optimization: degree and worst-case convergence rate
- Efficient simplicial replacement of semialgebraic sets
- Algorithm 976
- Efficient computation of a semi-algebraic basis of the first homology group of a semi-algebraic set
- Title not available (Why is that?)
- Conormal spaces and Whitney stratifications
- Computing the homology functor on semi-algebraic maps and diagrams
- Massively parallel computation of tropical varieties, their positive part, and tropical Grassmannians
- On generalizing Descartes' rule of signs to hypersurfaces
- Improved effective Łojasiewicz inequality and applications
- Persistent Homology of Semialgebraic Sets
- Title not available (Why is that?)
- Verification complexity of linear prime ideals
- Title not available (Why is that?)
- Vandermonde varieties, mirrored spaces, and the cohomology of symmetric semi-algebraic sets
- On the complexity of analyticity in semi-definite optimization
- Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location
This page was built for publication: Algorithms in real algebraic geometry: a survey
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4604289)
