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 quanti-fier 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 D O(d(n−d)) have been proposed. However, no implementation reflecting this complexity gain has been obtained and the constant in the exponent remains unspecified. We design a probabilistic algorithm which runs in time which is essentially cubic in D d(n−d). Our algorithm takes advantage of gener-icity properties of polar varieties to avoid computationally difficult steps of quantifier elimination. We also report on a first implementation. It tackles examples that are out of reach of the state-of-the-art and its practical behavior reflects the complexity gain.
ISSAC'15 Proceedings of the 40th International Symposium on Symbolic and Algebraic Computation https://hal.archives-ouvertes.fr/hal-01152751 Proceedings of the 40th International Symposium on Symbolic and Algebraic Computation, Jul 2015, Bath, United Kingdom. ACM, ISSAC'15, 2015, <10.1145/2755996.2756670>ARRAY(0x7f03fe8b95f0) 2015-07-06