On the complexity of computing real radicals of polynomial systems - Archive ouverte HAL Access content directly
Conference Papers Year :

On the complexity of computing real radicals of polynomial systems

(1) , (2) , (2)
1
2
Mohab Safey El Din
Lihong Zhi
  • Function : Author
  • PersonId : 863556

Abstract

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.
Fichier principal
Vignette du fichier
SaYaZhi18.pdf (375.03 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01956596 , version 1 (16-12-2018)

Identifiers

Cite

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⟩
54 View
339 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More