Computing Comprehensive Grobner Systems: A Comparison of Two Methods
In this paper, we consider two main approaches to compute Gr\"obner bases for parametric polynomial ideals, namely the {\sc DisPGB} algorithm developed by Montes \cite{monts1} and the {\sc PGBMain} proposed by Kapur, Sun and Wang \cite{kapur}. The former algorithm creates new branches in the s...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Vladimir Andrunachievici Institute of Mathematics and Computer Science
2017-12-01
|
| Series: | Computer Science Journal of Moldova |
| Subjects: | |
| Online Access: | http://www.math.md/files/csjm/v25-n3/v25-n2-(pp278-302).pdf |
| _version_ | 1798024173608501248 |
|---|---|
| author | Amir Hashemi Benyamin M.-Alizadeh Mahdi Dehghani Darmian |
| author_facet | Amir Hashemi Benyamin M.-Alizadeh Mahdi Dehghani Darmian |
| author_sort | Amir Hashemi |
| collection | DOAJ |
| description | In this paper, we consider two main approaches to compute Gr\"obner bases for parametric polynomial ideals, namely the {\sc DisPGB} algorithm developed by Montes \cite{monts1} and the {\sc PGBMain} proposed by Kapur, Sun and Wang \cite{kapur}. The former algorithm creates new branches in the space of parameters during the construction of Gr\"obner basis of a given ideal in the polynomial ring of variables and the latter computes (at each iteration) a Gr\"obner basis of the ideal in the polynomial ring of the variables and parameters and creates new branches according to leading coefficients in terms of parameters. Therefore, the latter algorithm can benefit from the efficient implementation of Gr\"obner basis algorithm in each computer algebra system. In order to compare these two algorithms (in the same platform) we use the recent algorithm namely GVW due to Gao et al. \cite{Gao2} to compute Gr\"obner bases which makes the use of the F$_5$ criteria proposed by Faug\`ere to remove superfluous reductions \cite{F5}. We show that there exists a class of examples so that an {\em incremental} structure on the {\sc DisPGB} algorithm by using the GVW algorithm is faster than the {\sc PGBMain} by applying the same algorithm to compute Gr\"obner bases. The mentioned algorithms have been implemented in {\tt Maple} and experimented with a number of examples. |
| first_indexed | 2024-04-11T17:59:17Z |
| format | Article |
| id | doaj.art-f727b1579f684457aedd6f9f0acca6ec |
| institution | Directory Open Access Journal |
| issn | 1561-4042 |
| language | English |
| last_indexed | 2024-04-11T17:59:17Z |
| publishDate | 2017-12-01 |
| publisher | Vladimir Andrunachievici Institute of Mathematics and Computer Science |
| record_format | Article |
| series | Computer Science Journal of Moldova |
| spelling | doaj.art-f727b1579f684457aedd6f9f0acca6ec2022-12-22T04:10:35ZengVladimir Andrunachievici Institute of Mathematics and Computer ScienceComputer Science Journal of Moldova1561-40422017-12-01253(75)278302Computing Comprehensive Grobner Systems: A Comparison of Two MethodsAmir Hashemi 0Benyamin M.-Alizadeh1Mahdi Dehghani Darmian2Department of Mathematical Sciences, Isfahan University of Technology, Isfahan, 84156-83111, IranSchool of Mathematics and Computer Sciences, Damghan University, Damghan, 36716-41167, IranSchool of Mathematics, Institute for Research in Fundamental Sciences (IPM), Tehran, 19395-5746, IranIn this paper, we consider two main approaches to compute Gr\"obner bases for parametric polynomial ideals, namely the {\sc DisPGB} algorithm developed by Montes \cite{monts1} and the {\sc PGBMain} proposed by Kapur, Sun and Wang \cite{kapur}. The former algorithm creates new branches in the space of parameters during the construction of Gr\"obner basis of a given ideal in the polynomial ring of variables and the latter computes (at each iteration) a Gr\"obner basis of the ideal in the polynomial ring of the variables and parameters and creates new branches according to leading coefficients in terms of parameters. Therefore, the latter algorithm can benefit from the efficient implementation of Gr\"obner basis algorithm in each computer algebra system. In order to compare these two algorithms (in the same platform) we use the recent algorithm namely GVW due to Gao et al. \cite{Gao2} to compute Gr\"obner bases which makes the use of the F$_5$ criteria proposed by Faug\`ere to remove superfluous reductions \cite{F5}. We show that there exists a class of examples so that an {\em incremental} structure on the {\sc DisPGB} algorithm by using the GVW algorithm is faster than the {\sc PGBMain} by applying the same algorithm to compute Gr\"obner bases. The mentioned algorithms have been implemented in {\tt Maple} and experimented with a number of examples.http://www.math.md/files/csjm/v25-n3/v25-n2-(pp278-302).pdfComprehensive Grobner systemsDisPGB algorithmPGBMain algorithmF5 criteriaGVW algorithm |
| spellingShingle | Amir Hashemi Benyamin M.-Alizadeh Mahdi Dehghani Darmian Computing Comprehensive Grobner Systems: A Comparison of Two Methods Computer Science Journal of Moldova Comprehensive Grobner systems DisPGB algorithm PGBMain algorithm F5 criteria GVW algorithm |
| title | Computing Comprehensive Grobner Systems: A Comparison of Two Methods |
| title_full | Computing Comprehensive Grobner Systems: A Comparison of Two Methods |
| title_fullStr | Computing Comprehensive Grobner Systems: A Comparison of Two Methods |
| title_full_unstemmed | Computing Comprehensive Grobner Systems: A Comparison of Two Methods |
| title_short | Computing Comprehensive Grobner Systems: A Comparison of Two Methods |
| title_sort | computing comprehensive grobner systems a comparison of two methods |
| topic | Comprehensive Grobner systems DisPGB algorithm PGBMain algorithm F5 criteria GVW algorithm |
| url | http://www.math.md/files/csjm/v25-n3/v25-n2-(pp278-302).pdf |
| work_keys_str_mv | AT amirhashemi computingcomprehensivegrobnersystemsacomparisonoftwomethods AT benyaminmalizadeh computingcomprehensivegrobnersystemsacomparisonoftwomethods AT mahdidehghanidarmian computingcomprehensivegrobnersystemsacomparisonoftwomethods |