KMS Of Academy of mathematics and systems sciences, CAS
Computing real radicals and S-radicals of polynomial systems | |
El Din, Mohab Safey1; Yang, Zhi-Hong2,3; Zhi, Lihong4,5 | |
2021 | |
Source Publication | JOURNAL OF SYMBOLIC COMPUTATION |
ISSN | 0747-7171 |
Volume | 102Pages:259-278 |
Abstract | Let 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. |
Keyword | Polynomial system Real radical S-radical ideal Semi-algebraic set Real algebraic geometry |
DOI | 10.1016/j.jsc.2019.10.018 |
Indexed By | SCI |
Language | 英语 |
Funding Project | ANR[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 Area | Computer Science ; Mathematics |
WOS Subject | Computer Science, Theory & Methods ; Mathematics, Applied |
WOS ID | WOS:000557877300014 |
Publisher | ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD |
Citation statistics | |
Document Type | 期刊论文 |
Identifier | http://ir.amss.ac.cn/handle/2S8OKBNM/51989 |
Collection | 系统科学研究所 |
Corresponding Author | El Din, Mohab Safey |
Affiliation | 1.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. |
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment