Computing the homology of basic semialgebraic sets in weak exponential time
From MaRDI portal
Abstract: We describe and analyze an algorithm for computing the homology (Betti numbers and torsion coefficients) of basic semialgebraic sets which works in weak exponential time. That is, out of a set of exponentially small measure in the space of data the cost of the algorithm is exponential in the size of the data. All algorithms previously proposed for this problem have a complexity which is doubly exponential (and this is so for almost all data).
Recommendations
Cited in
(23)- Description of the connected components of a semialgebraic set in single exponential time
- Probabilistic condition number estimates for real polynomial systems. I: A broader family of distributions
- Learning algebraic varieties from samples
- \(\mathbb{Z}_2\)-homology of weak \((p-2)\)-faceless \(p\)-pseudomanifolds may be computed in \(O(n)\) time
- Computing the homology of semialgebraic sets. II: General formulas
- Vandermonde varieties, mirrored spaces, and the cohomology of symmetric semi-algebraic sets
- On the complexity of the Plantinga-Vegter algorithm
- Computing the homology of semialgebraic sets. I: Lax formulas
- Computing the first few Betti numbers of semi-algebraic sets in single exponential time
- Smoothed analysis for the condition number of structured real polynomial systems
- Functional norms, condition numbers and numerical algorithms in algebraic geometry
- scientific article; zbMATH DE number 7559240 (Why is no real title available?)
- Sampling and homology via bottlenecks
- Computing Geometric Feature Sizes for Algebraic Manifolds
- Persistent Homology of Semialgebraic Sets
- Efficient simplicial replacement of semialgebraic sets
- The persistent topology of optimal transport based metric thickenings
- Efficient computation of a semi-algebraic basis of the first homology group of a semi-algebraic set
- Condition and homology in semialgebraic geometry
- Computing the homology functor on semi-algebraic maps and diagrams
- Computing the homology of real projective sets
- On the computation of the homology of semialgebraic sets
- Some lower bounds on the reach of an algebraic variety
This page was built for publication: Computing the homology of basic semialgebraic sets in weak exponential time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4625671)
