Algorithms for computing greatest common divisors of parametric multivariate polynomials

doi:10.1016/j.jsc.2019.10.006

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

	Algorithms for computing greatest common divisors of parametric multivariate polynomials
	Kapur, Deepak 3; Lu, Dong 4,5; Monagan, Michael 6; Sun, Yao 7; Wang, Dingkang 1,2
刊名	JOURNAL OF SYMBOLIC COMPUTATION
	2021
卷号	102 页码:3-20
关键词	Parametric multivariate polynomials Gcd system Minimal comprehensive Grobner system Ideal intersection Ideal quotient
ISSN号	0747-7171
DOI	10.1016/j.jsc.2019.10.006
英文摘要	Two new efficient algorithms for computing greatest common divisors (gcds) of parametric multivariate polynomials over k[U][X] are presented. The key idea of the first algorithm is that the gcd of two non-parametric multivariate polynomials can be obtained by dividing their product by the generator of the intersection of two principal ideals generated by the polynomials. The second algorithm is based on another simple insight that the gcd can be extracted using the generator of the ideal quotient of a polynomial with respect to the second polynomial. Since the ideal intersection and ideal quotient in these cases are also principal ideals, their generators can be obtained by computing minimal Grobner bases of the ideal intersection and ideal quotient, respectively. To avoid introducing new variables which can adversely affect the efficiency, minimal Grobner bases computations are performed on modules. Both of these constructions generalize to the parametric case as shown in the paper. Comprehensive Grobner system constructions are used for the parametric ideal intersection and ideal quotient using the Kapur-Sun-Wang's algorithm. It is proved that whether in a minimal comprehensive Grobner system of a parametric ideal intersection or in that of a parametric ideal quotient, each branch of the specializations corresponds to a principal parametric ideal with a single generator. Using this generator, the parametric gcd of that branch is obtained by division. For the case of more than two parametric polynomials, we can use the above two algorithms to compute gcds recursively, and get an extended algorithm by generalizing the idea of the second algorithm. Algorithms do not suffer from having to apply expensive steps such as ensuring whether parametric polynomials are primitive w.r.t. the main variable as used in both the algorithms proposed by Nagasaka (ISSAC, 2017). The resulting algorithms are not only conceptually simple to understand but are more efficient in practice. The proposed algorithms and both of Nagasaka's algorithms have been implemented in Singular, and their performance is compared on a number of examples. (C) 2019 Elsevier Ltd. All rights reserved.
资助项目	National Natural Science Foundation of China[11371356] ; National Natural Science Foundation of China[61877058] ; Chinese Academy of Sciences Key Project[QYZDJ-SSWSYS022] ; National Science Foundation[DMS-1217054] ; CAS-SAFEA International Partnership Program for Creative Research Teams ; Beijing Advanced Innovation Center for Big Data and Brain Computing, Beihang University ; [AQ-1701]
WOS研究方向	Computer Science ; Mathematics
语种	英语
出版者	ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD
WOS记录号	WOS:000557877300002
内容类型	期刊论文
源URL	[http://ir.amss.ac.cn/handle/2S8OKBNM/51991]
专题	系统科学研究所
通讯作者	Kapur, Deepak
作者单位	1.Chinese Acad Sci, Acad Math & Syst Sci, KLMM, Beijing 100190, Peoples R China 2.Univ Chinese Acad Sci, Sch Math Sci, Beijing 100049, Peoples R China 3.Univ New Mexico, Dept Comp Sci, Albuquerque, NM 87131 USA 4.Beihang Univ, Sch Math & Syst Sci, Beijing 100191, Peoples R China 5.Beihang Univ, Beijing Adv Innovat Ctr Big Data & Brain Comp, Beijing 100191, Peoples R China 6.Simon Fraser Univ, Dept Math, Burnaby, BC V5A 1S6, Canada 7.Chinese Acad Sci, Inst Informat Engn, SKLOIS, Beijing 100093, Peoples R China
推荐引用方式 GB/T 7714	Kapur, Deepak,Lu, Dong,Monagan, Michael,et al. Algorithms for computing greatest common divisors of parametric multivariate polynomials[J]. JOURNAL OF SYMBOLIC COMPUTATION,2021,102:3-20.
APA	Kapur, Deepak,Lu, Dong,Monagan, Michael,Sun, Yao,&Wang, Dingkang.(2021).Algorithms for computing greatest common divisors of parametric multivariate polynomials.JOURNAL OF SYMBOLIC COMPUTATION,102,3-20.
MLA	Kapur, Deepak,et al."Algorithms for computing greatest common divisors of parametric multivariate polynomials".JOURNAL OF SYMBOLIC COMPUTATION 102(2021):3-20.