On the complexity of computing real radicals of polynomial systems

Mohab Safey El Din (1) , Zhi-Hong Yang (2) , Lihong Zhi (2)

1 PolSys - Polynomial Systems
2 KLMM - Key Laboratory of Mathematics Mechanization

Let f= (f1, ..., fs) be a sequence of polynomials in Q[X1,...,Xn] of maximal degree D and V⊂ Cn be the algebraic set defined by f and r be its dimension. The real radical re < f > associated to f is the largest ideal which defines the real trace of V . When V is smooth, we show that re < f >, has a finite set of generators with degrees bounded by V. Moreover, we present a probabilistic algorithm of complexity (snDn )O(1) to compute the minimal primes of re < f >. When V is not smooth, we give a probabilistic algorithm of complexity sO(1) (nD)O(nr2r) to compute rational parametrizations for all irreducible components of the real algebraic set V ∩ Rn. Experiments are given to show the efficiency of our approaches.

Domaines: Calcul formel [cs.SC]

Mohab Safey El Din, Zhi-Hong Yang, Lihong Zhi. On the complexity of computing real radicals of polynomial systems. ISSAC '18 - The 2018 ACM on International Symposium on Symbolic and Algebraic Computation, Jul 2018, New-York, United States. pp.351-358, ⟨10.1145/3208976.3209002⟩. ⟨hal-01956596⟩