KMS Of Academy of mathematics and systems sciences, CAS
Algorithms for computing greatest common divisors of parametric multivariate polynomials | |
Kapur, Deepak1; Lu, Dong2,3; Monagan, Michael4; Sun, Yao5; Wang, Dingkang6,7 | |
2021 | |
Source Publication | JOURNAL OF SYMBOLIC COMPUTATION |
ISSN | 0747-7171 |
Volume | 102Pages:3-20 |
Abstract | 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. |
Keyword | Parametric multivariate polynomials Gcd system Minimal comprehensive Grobner system Ideal intersection Ideal quotient |
DOI | 10.1016/j.jsc.2019.10.006 |
Indexed By | SCI |
Language | 英语 |
Funding Project | 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 Research Area | Computer Science ; Mathematics |
WOS Subject | Computer Science, Theory & Methods ; Mathematics, Applied |
WOS ID | WOS:000557877300002 |
Publisher | ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD |
Citation statistics | |
Document Type | 期刊论文 |
Identifier | http://ir.amss.ac.cn/handle/2S8OKBNM/51992 |
Collection | 系统科学研究所 |
Corresponding Author | Kapur, Deepak |
Affiliation | 1.Univ New Mexico, Dept Comp Sci, Albuquerque, NM 87131 USA 2.Beihang Univ, Beijing Adv Innovat Ctr Big Data & Brain Comp, Beijing 100191, Peoples R China 3.Beihang Univ, Sch Math & Syst Sci, Beijing 100191, Peoples R China 4.Simon Fraser Univ, Dept Math, Burnaby, BC V5A 1S6, Canada 5.Chinese Acad Sci, Inst Informat Engn, SKLOIS, Beijing 100093, Peoples R China 6.Chinese Acad Sci, Acad Math & Syst Sci, KLMM, Beijing 100190, Peoples R China 7.Univ Chinese Acad Sci, Sch Math Sci, Beijing 100049, Peoples R China |
Recommended Citation 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. |
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