Computing the Homology of Semialgebraic Sets. I : Lax Formulas

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

View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)71-118
Journal / PublicationFoundations of Computational Mathematics
Volume20
Issue number1
Online published6 May 2019
Publication statusPublished - Feb 2020

Abstract

We describe and analyze an algorithm for computing the homology (Betti numbers and torsion coefficients) of closed semialgebraic sets given by Boolean formulas without negations over lax polynomial inequalities. 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. All previous algorithms solving this problem have doubly exponential complexity. Our algorithm thus represents an exponential acceleration over state-of-the-art algorithms for all input data outside a set that vanishes exponentially fast.

Research Area(s)

  • Homology groups, Numerical algorithms, Weak complexity

Citation Format(s)

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

In: Foundations of Computational Mathematics, Vol. 20, No. 1, 02.2020, p. 71-118.

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