Computing Comprehensive Grobner Systems: A Comparison of Two Methods

Abstract

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.

Keywords

• Comprehensive Grobner systems
• DisPGB algorithm
• PGBMain algorithm
• F5 criteria
• GVW algorithm