Algorithms in real algebraic geometry: a survey

MaRDI QIDQ4604289zbMATH OpenFDO

Authors Saugata Basu

Publication date 23 February 2018

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

zbMATH Keywords

algorithmscomplexityBetti numbersquantifier eliminationsemi-algebraic setsroadmaps

Mathematics Subject Classification ID

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)

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.

Recommendations

• scientific article; zbMATH DE number 953041
• scientific article; zbMATH DE number 2209741
• Algorithms in real algebraic geometry
• scientific article; zbMATH DE number 66679
• scientific article; zbMATH DE number 10786

Cited in

(26)

• Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location
• scientific article; zbMATH DE number 66679 (Why is no real title available?)
• Some aspects of complexity in real algebraic geometry
• Algorithms in real algebraic geometry
• Algorithms in real algebraic geometry
• scientific article; zbMATH DE number 27176 (Why is no real title available?)
• 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
• scientific article; zbMATH DE number 2209741 (Why is no real title available?)
• 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
• scientific article; zbMATH DE number 1023365 (Why is no real title available?)
• Conormal spaces and Whitney stratifications
• Computing the homology functor on semi-algebraic maps and diagrams
• On generalizing Descartes' rule of signs to hypersurfaces
• Massively parallel computation of tropical varieties, their positive part, and tropical Grassmannians
• Improved effective Łojasiewicz inequality and applications
• scientific article; zbMATH DE number 939818 (Why is no real title available?)
• Persistent Homology of Semialgebraic Sets
• Verification complexity of linear prime ideals
• scientific article; zbMATH DE number 1984321 (Why is no real title available?)
• Vandermonde varieties, mirrored spaces, and the cohomology of symmetric semi-algebraic sets
• On the complexity of analyticity in semi-definite optimization

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)