Computing the homology of semialgebraic sets. II: General formulas
The authors exhibit a numerical algorithm for computing the homology (Betti numbers and torsion coefficients) of semialgebraic sets given by Boolean formulas. This work extends to arbitrary semialgebraic sets the results in part I [\textit{P. Bürgisser} et al., Found. Comput. Math. 20, No. 1, 71--118 (2020; Zbl 1440.14264)]. Complements are allowed in the Boolean combinations (or, equivalently, negations in the Boolean formulas) describing semialgebraic sets and so are strict inequalities. The new algorithm works in weak exponential time. This means that its cost, or running time, is single exponential outside an exceptional set whose measure vanishes exponentially fast. Outside this exceptional set then, the algorithm works exponentially faster than state-of-the-art algorithms (which are doubly exponential).
- Computing the homology of semialgebraic sets. I: Lax formulas
- Computing the homology of basic semialgebraic sets in weak exponential time
- scientific article; zbMATH DE number 1256759
- Computing the homology of real projective sets
- Computing the first few Betti numbers of semi-algebraic sets in single exponential time
- A numerical algorithm for zero counting. I: Complexity and accuracy
- Approximation of definable sets by compact families, and upper bounds on homotopy and homology
- Complexity of Bezout’s Theorem IV: Probability of Success; Extensions
- Computing the homology of basic semialgebraic sets in weak exponential time
- Computing the homology of real projective sets
- Computing the homology of semialgebraic sets. I: Lax formulas
- Condition. The geometry of numerical algorithms
- Finding the homology of submanifolds with high confidence from random samples
- scientific article; zbMATH DE number 3497890 (Why is no real title available?)
- scientific article; zbMATH DE number 3564960 (Why is no real title available?)
- scientific article; zbMATH DE number 3992817 (Why is no real title available?)
- scientific article; zbMATH DE number 2103273 (Why is no real title available?)
- Notes on topological stability
- Numerical instability of resultant methods for multidimensional rootfinding
- On the Piano Movers problem. II: General techniques for computing topological properties of real algebraic manifolds
- Probabilistic condition number estimates for real polynomial systems. I: A broader family of distributions
- Topological stability of smooth mappings
- On the complexity of the Plantinga-Vegter algorithm
- Recent advances in the computation of the homology of semialgebraic sets
- Computing the homology of semialgebraic sets. I: Lax formulas
- Computing the first few Betti numbers of semi-algebraic sets in single exponential time
- Guaranteeing the homotopy type of a set defined by non-linear inequalities
- Computation with semialgebraic sets represented by cylindrical algebraic formulas
- Homology classes of semi-algebraic sets and mass minimization
- Computing Roadmaps of Semi-algebraic Sets on a Variety (Extended Abstract)
- Computing the homology of basic semialgebraic sets in weak exponential time
- Functional norms, condition numbers and numerical algorithms in algebraic geometry
- Sampling and homology via bottlenecks
- The critical curvature degree of an algebraic variety
- Persistent Homology of Semialgebraic Sets
- Efficient simplicial replacement of semialgebraic sets
- 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 semialgebraic sets. II: General formulas
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2052718)
