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.

• Speaker: Peter Bürgisser (TU Berlin)
• Thursday 25 January 2018, 15:00–16:00
• Venue: MR14, Centre for Mathematical Sciences.
• Series: Applied and Computational Analysis; organiser: Hamza Fawzi.