Search

Workshop

Numerical computation of the homology of basic semialgebraic sets

  • Pierre Lairez (INRIA Saclay Île-de-France)
E1 05 (Leibniz-Saal)

Abstract

Semialgebraic sets (that is subsets of Euclidean spaces defined by polynomial equations and inequalities) come in a wide variety of shapes. This raises the problem of describing a given specimen, from basic features like the number of connected components, to finer ones, like homology.

Following a well-known approach, we compute the homology using approximations by point cloud. We show how to ensure correctness and give complexity bounds in terms of the conditioning of the input equations. A probabilistic analysis shows that outside of a vanishingly small subset of the input space, the complexity is single exponential with respect to the number of variables. This improves upon the previously-known double exponential complexity bounds.

Links

Saskia Gutzschebauch

Max-Planck-Institut für Mathematik in den Naturwissenschaften Contact via Mail

Christiane Görgen

Max-Planck-Institut für Mathematik in den Naturwissenschaften

Sara Kališnik Verovšek

Max-Planck-Institut für Mathematik in den Naturwissenschaften

Vlada Limic

Université de Strasbourg and CNRS, Paris