Computing the Homology of Semialgebraic Sets. II: General Formulas

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 th...

Full description

Saved in:
Bibliographic Details
Published in:Foundations of computational mathematics 2021-10, Vol.21 (5), p.1279-1316
Main Authors: Bürgisser, Peter, Cucker, Felipe, Tonelli-Cueto, Josué
Format: Article
Language:English
Subjects:
Algebraic Geometry
Algorithms
Applications of Mathematics
Boolean algebra
Computation
Computational Geometry
Computer Science
Economics
Homology
Linear and Multilinear Algebras
Math Applications in Computer Science
Mathematics
Mathematics and Statistics
Matrix Theory
Numerical Analysis
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1615-3375
1615-3383
DOI:10.1007/s10208-020-09483-8