Computing the Homology of Semialgebraic Sets. II : General Formulas

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)1279–1316
Number of pages38
Journal / PublicationFoundations of Computational Mathematics
Volume21
Issue number5
Online published4 Jan 2021
Publication statusPublished - Oct 2021

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.

Research Area(s)

  • Homology groups, Numerical algorithms, Semialgebraic sets, Weak complexity

Citation Format(s)

Computing the Homology of Semialgebraic Sets. II : General Formulas. / Bürgisser, Peter; Cucker, Felipe; Tonelli-Cueto, Josué.

In: Foundations of Computational Mathematics, Vol. 21, No. 5, 10.2021, p. 1279–1316.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review