An efficient method for computing comprehensive Grobner bases

摘要

A new approach is proposed for computing a comprehensive Grobner basis of a parameterized polynomial system. The key new idea is not to simplify a polynomial under various specialization of its parameters, but rather keep track in the polynomial, of the power products whose coefficients vanish; this is achieved by partitioning the polynomial into two parts-nonzero part and zero part for the specialization under consideration. During the computation of a comprehensive Grobner system, for a particular branch corresponding to a specialization of parameter values, nonzero parts of the polynomials dictate the computation, i.e., computing S-polynomials as well as for simplifying a polynomial with respect to other polynomials; but the manipulations on the whole polynomials (including their zero parts) are also performed. Once a comprehensive Grobner system is generated, both nonzero and zero parts of the polynomials are collected from every branch and the result is a faithful comprehensive Grobner basis, to mean that every polynomial in a comprehensive Grobner basis belongs to the ideal of the original parameterized polynomial system. This technique should be applicable to all algorithms for computing a comprehensive Grobner system, thus producing both a comprehensive Grobner system as well as a faithful comprehensive Grobner basis of a parameterized polynomial system simultaneously. To propose specific algorithms for computing comprehensive Grobner bases, a more generalized theorem is presented to give a more generalized stable condition for parametric polynomial systems. Combined with the new approach, the new theorem leads to two efficient algorithms for computing comprehensive Grobner bases. The timings on a collection of examples demonstrate that both these two new algorithms for computing comprehensive Grobner bases have better performance than other existing algorithms.