Computing the Dimension of Real Algebraic Sets
Pierre Lairez, Mohab Safey El Din · 2021
Let V be the set of real common solutions to F = (f1, …, fs) in ℜ[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.