Computing the Homology of Semialgebraic Sets. II: General formulas

Abstract

We describe and analyze a numerical algorithm for computing the homology (Betti numbers and torsion coefficients) of semialgebraic sets given by Boolean formulas. The algorithm works in weak exponential time. This means that outside a subset of data having exponentially small measure, the cost of the algorithm is single exponential in the size of the data. This extends the previous work of the authors in arXiv:1807.06435 to arbitrary semialgebraic sets. All previous algorithms proposed for this problem have doubly exponential complexity.

arXiv comment33 pages, 4 figures

References in corpus (5)

• A Numerical Algorithm for Zero Counting. I: Complexity and Accuracy
• Approximation of definable sets by compact families, and upper bounds on homotopy and homology
• Computing the homology of basic semialgebraic sets in weak exponential time
• Computing the Homology of Semialgebraic Sets I: Lax Formulas
• Probabilistic Condition Number Estimates For Real Polynomial Systems I: A Broader Family Of Distributions

Cited by in corpus (3)

• Vandermonde varieties, mirrored spaces, and the cohomology of symmetric semi-algebraic sets
• On the Complexity of the Plantinga-Vegter Algorithm
• Functional norms, condition numbers and numerical algorithms in algebraic geometry