10/03/2014

Speaker(s) : Ivan Bannwarth (PolSys team, CNRS/INRIA/UPMC)

We consider the problem of computing the emph{real dimension} of a semi-algebraic set $S$. The real dimension of $S$ is the maximal integer $d$ such that the projection of $S$ over a $d$-dimensional affine subspace of coordinates has dimension $d$.

Since quantifier elimination (QE) of one block of variables over the reals consists in computing the projection of a semi-algebraic set, QE plays a prominent role in algorithms for computing the real dimension of $S$. Hence, the cylindrical algebraic decomposition algorithm, due to Collins, can be used to compute the real dimension of $S$ within a complexity which is doubly exponential in the number of variables. Later on, Koiran, Vorobjov, and Basu, Pollack and Roy took advantage on recent progress on QE when there is a single block of variables to eliminate. This yields a family of deterministic algorithms with arithmetic complexity $((s+1)D)^{O(d(n-d))}$ (where the input consists of $n$-variate polynomials of degree $leq D$ involving $s$ inequalities).

Despite the improvement of the complexity class, there is no implementation revealing the complexity gain ; one bottleneck being to have a good control on the complexity constant in the exponent. Up to now, it seemed that the best implementations for computing the real dimension are based on the cylindrical algebraic decomposition algorithm. Our goal is to design new algorithms for computing the real dimension of semi-algebraic sets whose complexity lies in the best known complexity class and whose practical behavior reflects the complexity gain. One approach to do that is to control the complexity constant in the exponent.

In this talk, we study the particular case of real algebraic sets. We will describe a emph{probabilistic} algorithm for computing the real dimension of real algebraic sets in time $Olog (Ln^{15}D^{3(n-d)d +6n+3})$ (where $L$ is the complexity of evaluating the input). Our algorithm takes advantage of properties of emph{polar varieties} to avoid computationally difficult steps in QE when studying the projections of the real algebraic set under study. We also report on a first implementation of this algorithm in Maple using Gröbner bases for algebraic elimination operations. This preliminary implementation tackles examples that are out of reach of the state-of-the-art.

Joint work with Mohab Safey El Din.

Elias.Tsigaridas (at) nulllip6.fr