Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleAn efficient method for computing comprehensive Gröbner bases
Author(s) Deepak Kapur, Yao Sun, Dongming Wang
TypeArticle in Journal
AbstractA new approach is proposed for computing a comprehensive Gröbner 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 Gröbner 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 Gröbner system is generated, both nonzero and zero parts of the polynomials are collected from every branch and the result is a faithful comprehensive Gröbner basis, to mean that every polynomial in a comprehensive Gröbner basis belongs to the ideal of the original parameterized polynomial system. This technique should be applicable to all algorithms for computing a comprehensive Gröbner system, thus producing both a comprehensive Gröbner system as well as a faithful comprehensive Gröbner basis of a parameterized polynomial system simultaneously. To propose specific algorithms for computing comprehensive Gröbner 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 Gröbner bases. The timings on a collection of examples demonstrate that both these two new algorithms for computing comprehensive Gröbner bases have better performance than other existing algorithms.
KeywordsGröbner basis, Comprehensive Gröbner basis, Comprehensive Gröbner system, Stability condition
URL http://www.sciencedirect.com/science/article/pii/S0747717112001320
JournalJournal of Symbolic Computation
Pages124 - 142
NoteInternational Symposium on Symbolic and Algebraic Computation
Translation No
Refereed No