Name
Abstract | ||
|---|---|---|
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. We design a probabilistic algorithm which runs in time which is essentially cubic in Dd(n-d). Our algorithm takes advantage of genericity 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. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1145/2755996.2756670 | Proceedings of the 2015 ACM on International Symposium on Symbolic and Algebraic Computation |
Keywords | DocType | Citations |
theory,real dimension | Conference | 2 |
PageRank | References | Authors |
0.37 | 24 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| ivan bannwarth | 1 | 2 | 0.37 |
| Mohab Safey El Din | 2 | 450 | 35.64 |