CSpace  > 系统科学研究所
Algorithms for computing greatest common divisors of parametric multivariate polynomials
Kapur, Deepak1; Lu, Dong2,3; Monagan, Michael4; Sun, Yao5; Wang, Dingkang6,7
2021
Source PublicationJOURNAL OF SYMBOLIC COMPUTATION
ISSN0747-7171
Volume102Pages:3-20
AbstractTwo 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.
KeywordParametric multivariate polynomials Gcd system Minimal comprehensive Grobner system Ideal intersection Ideal quotient
DOI10.1016/j.jsc.2019.10.006
Indexed BySCI
Language英语
Funding ProjectNational 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 AreaComputer Science ; Mathematics
WOS SubjectComputer Science, Theory & Methods ; Mathematics, Applied
WOS IDWOS:000557877300002
PublisherACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD
Citation statistics
Document Type期刊论文
Identifierhttp://ir.amss.ac.cn/handle/2S8OKBNM/51992
Collection系统科学研究所
Corresponding AuthorKapur, Deepak
Affiliation1.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.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Kapur, Deepak]'s Articles
[Lu, Dong]'s Articles
[Monagan, Michael]'s Articles
Baidu academic
Similar articles in Baidu academic
[Kapur, Deepak]'s Articles
[Lu, Dong]'s Articles
[Monagan, Michael]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Kapur, Deepak]'s Articles
[Lu, Dong]'s Articles
[Monagan, Michael]'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.