@inproceedings{7dbfa66a94b14e2493c4c50e367d8389,
title = "Computing the Dimension of Real Algebraic Sets",
abstract = "Let V be the set of real common solutions to F = (f1, ⋯, fs) in R[x1, ⋯, xn] and D be the maximum total degree of the fi's. We design an algorithm which on input F computes the dimension of V. Letting L be the evaluation complexity of F and s=1, it runs using {\~O}(L D n(d+3)+1) arithmetic operations in and at most Dn(d+1) isolations of real roots of polynomials of degree at most Dn. Our algorithm depends on the real geometry of V; its practical behavior is more governed by the number of topology changes in the fibers of some well-chosen maps. Hence, the above worst-case bounds are rarely reached in practice, the factor Dnd being in general much lower on practical examples. We report on an implementation showing its ability to solve problems which were out of reach of the state-of-the-art implementations.",
keywords = "computer algebra, dimension, real algebraic set",
author = "Pierre Lairez and \{Safey El Din\}, Mohab",
note = "Publisher Copyright: {\textcopyright} 2021 ACM.; 46th International Symposium on Symbolic and Algebraic Computation, ISSAC 2021 ; Conference date: 18-07-2021 Through 23-07-2021",
year = "2021",
month = jul,
day = "18",
doi = "10.1145/3452143.3465551",
language = "English",
series = "Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC",
publisher = "Association for Computing Machinery",
pages = "257--264",
booktitle = "ISSAC 2021 - Proceedings of the 2021 International Symposium on Symbolic and Algebraic Computation",
}