Computing real radicals and S-radicals of polynomial systems. (January 2021)

• Record Type: Journal Article
• Authors: Safey El Din, Mohab; Yang, Zhi-Hong; Zhi, Lihong
• Is Part Of: Journal of symbolic computation. Volume 102(2020)
• Page Start: 259
• Page End: 278
• Publication Date: 2021-01
• Subjects: Polynomial system -- Real radical -- S-radical ideal -- Semi-algebraic set -- Real algebraic geometry; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2019.10.018
• Languages: English
• ISSNs: 0747-7171

Abstract

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.