An Algorithm to Check Whether a Basis of a Parametric Polynomial System is a Comprehensive Gröbner Basis and the Associated Completion Algorithm
Deepak Kapur, Yiming Yang · 2015
Given a basis of a parametric polynomial ideal, an algorithm is proposed to test whether it is a comprehensive Gröbner basis or not. A basis of a parametric polynomial ideal is a comprehensive Gröbner basis if and only if for every specialization of parameters in a given field, the specialization of the basis is a Gröbner basis of the associated specialized polynomial ideal. In case a basis does not check to be a comprehensive Gröbner basis, a completion algorithm for generating a comprehensive Gröbner basis from it that is patterned after Buchberger's algorithm is proposed. Its termination is proved and its correctness is established. In contrast to other algorithms for computing a comprehensive Gröbner basis which first compute a comprehensive Gröbner system and then extract a comprehensive Gröbner basis from it, the proposed algorithm computes a comprehensive Gröbner basis directly. Further, the proposed completion algorithm always computes a minimal faithful comprehensive Gröbner basis in the sense that every polynomial in the result is from the ideal as well as essential with respect to the comprehensive Gröbner basis. A prototype implementation of the algorithm has been successfully tried on many examples from the literature. An interesting and somewhat surprising outcome of using the proposed algorithm is that there are example parametric ideals for which a minimal comprehensive Gröbner basis computed by it is different from minimal comprehensive Gröbner bases computed by other algorithms in the literature.