Skip to Main content Skip to Navigation
Journal articles

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 work in Part I to arbitrary semialgebraic sets. All previous algorithms proposed for this problem have doubly exponential complexity .
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download

https://hal.inria.fr/hal-02878370
Contributor : Josué Tonelli-Cueto <>
Submitted on : Tuesday, June 23, 2020 - 10:02:56 AM
Last modification on : Wednesday, June 2, 2021 - 4:26:58 PM

File

Computing_the_Homology_of_Semi...
Files produced by the author(s)

Identifiers

Citation

Peter Bürgisser, Felipe Cucker, Josué Tonelli-Cueto. Computing the Homology of Semialgebraic Sets. II: General formulas. Foundations of Computational Mathematics, Springer Verlag, 2021, ⟨10.1007/s10208-020-09483-8⟩. ⟨hal-02878370⟩

Share

Metrics

Record views

83

Files downloads

349