Computing real radicals and S-radicals of polynomial systems

doi:10.1016/j.jsc.2019.10.018

CORC > 数学与系统科学研究院 > 中国科学院数学与系统科学研究院 > 系统科学研究所

	Computing real radicals and S-radicals of polynomial systems
	El Din, Mohab Safey 4; Yang, Zhi-Hong 3,5; Zhi, Lihong 1,2
刊名	JOURNAL OF SYMBOLIC COMPUTATION
	2021
卷号	102 页码:259-278
关键词	Polynomial system Real radical S-radical ideal Semi-algebraic set Real algebraic geometry
ISSN号	0747-7171
DOI	10.1016/j.jsc.2019.10.018
英文摘要	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.
资助项目	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研究方向	Computer Science ; Mathematics
语种	英语
出版者	ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD
WOS记录号	WOS:000557877300014
内容类型	期刊论文
源URL	[http://ir.amss.ac.cn/handle/2S8OKBNM/51988]
专题	系统科学研究所
通讯作者	El Din, Mohab Safey
作者单位	1.Chinese Acad Sci, Acad Math & Syst Sci, KLMM, Beijing 100190, Peoples R China 2.Univ Chinese Acad Sci, Beijing 100049, Peoples R China 3.Duke Univ, Dept Comp Sci, Durham, NC 27706 USA 4.Sorbonne Univ, Equipe PolSys, LIP6, INRIA,CNRS,Lab Informat Paris 6, 4 Pl Jussieu, F-75252 Paris 05, France 5.North Carolina State Univ, Dept Math, Raleigh, NC USA
推荐引用方式 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.