IMCS/Publications/CSJM/Issues/CSJM v.25, n.3 (75), 2017/

Computing Comprehensive Gröbner Systems: A Comparison of Two Methods

Authors: Amir Hashemi, Benyamin M.-Alizadeh, Mahdi Dehghani Darmian
Keywords: Comprehensive Gröbner systems, {\sc DisPGB} algorithm, {\sc PGBMain} algorithm, F$_5$ criteria, GVW algorithm.


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

Amir Hashemi
Department of Mathematical Sciences, Isfahan University of Technology
Isfahan, 84156-83111, Iran

Benyamin M.-Alizadeh
School of Mathematics and Computer Sciences, Damghan University
Damghan, 36716-41167, Iran

Mahdi Dehghani Darmian
School of Mathematics, Institute for Research in Fundamental Sciences (IPM)
Tehran, 19395-5746, Iran


Adobe PDF document0.21 Mb