Computing the homology of basic semialgebraic sets

With Peter Bürgisser (TU Berlin)

Computing the homology of basic semialgebraic sets

We describe a numerical algorithm for computing the homology (Betti numbers and torsion coefficients) of a basic semialgebraic set. The algorithm is numerically stable in the sense that the precision required to guarantee a correct output depends on the condition number of the data and it is polynomially small. Its running time also depends on this condition but it is bounded by a singly exponential bound on the size of the input out of a vanishingly small set of data. All algorithms previously proposed for this problem have a complexity which is doubly exponential (and this is so for almost all data).

This is joint work with Felipe Cucker and Pierre Lairez.

Add to your calendar or Include in your list

How can mathematics help us to understand the behaviour of ants? Read more about the fanscinating work being carri… View on Twitter