A signature-based algorithm for computing Gröbner bases in solvable polynomial algebras
Yao Sun, Dingkang Wang, Xiaodong Ma, Yang Zhang · 2012
Signature-based algorithms, including F5, F5C, G2V and GVW, are efficient algorithms for computing Gröbner bases in commutative polynomial rings. In this paper, we present a signature-based algorithm to compute Gröbner bases in solvable polynomial algebras which include usual commutative polynomial rings and some non-commutative polynomial rings like Weyl algebra. The generalized Rewritten Criterion (discussed in Sun and Wang, ISSAC 2011) is used to reject redundant computations. When this new algorithm uses the partial order implied by GVW, its termination is proved without special assumptions on computing orders of critical pairs. Data structures similar to F5 can be used to speed up this new algorithm, and Gröbner bases of syzygy modules of input polynomials can be obtained from the outputs easily. Experimental data show that most redundant computations can be avoided in this new algorithm.