Computing real radicals and S-radicals of polynomial systems. (January 2021) - Safey El Din, Mohab; Yang, Zhi-Hong; Zhi, Lihong
Abstract: Let f = ( f 1, …, f s ) be a sequence of polynomials in Q [ X 1, …, X n ] of maximal degree D and V ⊂ C n be the algebraic set defined by f and r be its dimension. The real radical 〈 f 〉 r e associated to f is the largest ideal which defines the real trace of V . When V is smooth, we show that 〈 f 〉 r e, has a finite set of generators with degrees bounded by deg ⁡ V . Moreover, we present a probabilistic algorithm of complexity ( s n D n ) O ( 1 ) to compute the minimal primes of 〈 f 〉 r e . When V is not smooth, we give a probabilistic algorithm of complexity s O ( 1 ) ( n D ) O ( n r 2 r ) to compute rational parametrizations for all irreducible components of the real algebraic set V ∩ R n . Let ( g 1, …, g p ) in Q [ X 1, …, X n ] and S be the basic closed semi-algebraic set defined by g 1 ≥ 0, …, g p ≥ 0 . The S -radical of 〈 f 〉, which is denoted by 〈 f 〉 S, is the ideal associated to the Zariski closure of V ∩ S . We give a probabilistic algorithm to compute rational parametrizations of all irreducible components of that Zariski closure, hence encoding 〈 f 〉 S . Assuming now that D is the maximum of the degrees of the f i 's and the g i 's, this algorithm runs in time 2 p ( s + p ) O ( 1 ) ( n D ) O ( r n 2 r ) . Experiments are performed to illustrate and show the efficiency of our approaches on computing real radicals.