Probabilistic Algorithm for Computing the Dimension of Real Algebraic Sets
Ivan Bannwarth, Mohab Safey El Din · 2015
Let fΕ Q[X1, …, Xn] be a polynomial of degree D. We consider the problem of computing the real dimension of the real algebraic set defined by f=0. Such a problem can be reduced to quantifier elimination. Hence it can be tackled with Cylindrical Algebraic Decomposition within a complexity that is doubly exponential in the number of variables. More recently, denoting by d the dimension of the real algebraic set under study, deterministic algorithms running in time DO(d(n-d)) have been proposed. However, no implementation reflecting this complexity gain has been obtained and the constant in the exponent remains unspecified.