CSpace  > 系统科学研究所
Computing real radicals and S-radicals of polynomial systems
El Din, Mohab Safey1; Yang, Zhi-Hong2,3; Zhi, Lihong4,5
AbstractLet f = (f(1), ..., f(s)) be a sequence of polynomials in Q[X-1, ..., X-n] of maximal degree D and V subset of C-n be the algebraic set defined by f and r be its dimension. The real radical re root < f > associated to f is the largest ideal which defines the real trace of V. When V is smooth, we show that re root < f >, has a finite set of generators with degrees bounded by deg V. Moreover, we present a probabilistic algorithm of complexity (snD(n))(O(1)) to compute the minimal primes of re root < f >. When V is not smooth, we give a probabilistic algorithm of complexity s(O(1))(nD)(O(nr2r)) to compute rational parametrizations for all irreducible components of the real algebraic set V boolean AND R-n. Let (g(1), ..., g(p)) in Q[X-1, ..., X-n] and S be the basic closed semialgebraic set defined by g(1) >= 0, ..., g(p) >= 0. The S-radical of < f >, which is denoted by s root < f >, is the ideal associated to the Zariski closure of V boolean AND S. We give a probabilistic algorithm to compute rational parametrizations of all irreducible components of that Zariski closure, hence encoding s root < f >. 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))(nD)(O(nr2r)). Experiments are performed to illustrate and show the efficiency of our approaches on computing real radicals. (C) 2019 Elsevier Ltd. All rights reserved.
KeywordPolynomial system Real radical S-radical ideal Semi-algebraic set Real algebraic geometry
Indexed BySCI
Funding ProjectANR[ANR-18-CE33-0011] ; PGMO grant Gamma ; European Union's Horizon 2020research and innovation programunder the Marie Sklodowska-Curie grant[813211] ; NSF[CCF-1717100] ; National Key Research Project of China[2018YFA0306702] ; National Natural Science Foundation of China[11571350]
WOS Research AreaComputer Science ; Mathematics
WOS SubjectComputer Science, Theory & Methods ; Mathematics, Applied
WOS IDWOS:000557877300014
Citation statistics
Document Type期刊论文
Corresponding AuthorEl Din, Mohab Safey
Affiliation1.Sorbonne Univ, Equipe PolSys, LIP6, INRIA,CNRS,Lab Informat Paris 6, 4 Pl Jussieu, F-75252 Paris 05, France
2.North Carolina State Univ, Dept Math, Raleigh, NC USA
3.Duke Univ, Dept Comp Sci, Durham, NC 27706 USA
4.Chinese Acad Sci, Acad Math & Syst Sci, KLMM, Beijing 100190, Peoples R China
5.Univ Chinese Acad Sci, Beijing 100049, Peoples R China
Recommended Citation
GB/T 7714
El Din, Mohab Safey,Yang, Zhi-Hong,Zhi, Lihong. Computing real radicals and S-radicals of polynomial systems[J]. JOURNAL OF SYMBOLIC COMPUTATION,2021,102:259-278.
APA El Din, Mohab Safey,Yang, Zhi-Hong,&Zhi, Lihong.(2021).Computing real radicals and S-radicals of polynomial systems.JOURNAL OF SYMBOLIC COMPUTATION,102,259-278.
MLA El Din, Mohab Safey,et al."Computing real radicals and S-radicals of polynomial systems".JOURNAL OF SYMBOLIC COMPUTATION 102(2021):259-278.
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[El Din, Mohab Safey]'s Articles
[Yang, Zhi-Hong]'s Articles
[Zhi, Lihong]'s Articles
Baidu academic
Similar articles in Baidu academic
[El Din, Mohab Safey]'s Articles
[Yang, Zhi-Hong]'s Articles
[Zhi, Lihong]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[El Din, Mohab Safey]'s Articles
[Yang, Zhi-Hong]'s Articles
[Zhi, Lihong]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.