Since the F5 algorithm is proposed, a bunch of signature-based Gr?bner basis algorithms appear. They use different selection strategies to get the basis gradually and use different criteria to discard redundant polynomials as many as possible. The strategies and criteria should satisfy some general rules for correct termination. Based on these rules, a framework which include many algorithms as instances is proposed. Using the property of rewrite basis, a simple proof of the correct termination of the framework is obtained. For the simple proof of the F5 algorithm, the reduction process is simplified. In particular, for homogeneous F5 algorithm, its complicated selection strategy is proved equivalent to selecting polynomials with respect to module order. In this way, the F5 algorithm can be seen as an instance of the framework and has a rather short proof.
Buchberger B. Ein algorithmus zum auffinden der basiselemente des restklassenrings nach einem nulldimensionalen polynomideal[D]. [Ph.D. dissertation], Universität Innsbruck, Austria, 1965.
[2]
Faugère J C. A new efficient algorithm for computing Gröbner bases (F4)[J]. Journal of Pure and Applied Algebra, 1999, 139(1-3): 61-88.
[3]
Faugère J C. A new efficient algorithm for computing Gröbner bases without reduction to zero (F5)[C]. Proceedings of the 27th International Symposium on Symbolic and Algebraic Computation, New York, USA, 2002: 75-83.
[4]
Arri A and Perry J. The F5 criterion revised[J]. Journal of Symbolic Computation, 2011, 46(9): 1017-1029.
[5]
Gao Shu-hong, Guan Yin-hua, and Volny F IV. A new incremental algorithm for computing Groebner bases[C]. Proceedings of the 35th International Symposium on Symbolic and Algebraic Computation, New York, USA, 2010: 13-19.
[6]
Gao Shu-hong, Volny F, and Wang Ming-sheng. A new algorithm for computing Gröbner bases[OL]. http://www. math.clemson.edu/~sgao/papers/gvw_R130704.pdf, 2010.
[7]
Volny F. New algorithms for computing Gröbner bases[D]. [Ph.D. dissertation], Clemson University, USA, 2011.
[8]
Sun Yao and Wang Ding-kang. A generalized criterion for signature related Gröbner basis algorithms[C]. Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation, New York, USA, 2011: 337-344.
[9]
Eder C and Perry J. Signature-based algorithms to compute Gröbner bases[C]. Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation, New York, USA, 2011: 99-106.
[10]
Pan Sen-shan, Hu Yu-pu, and Wang Bao-cang. The termination of the F5 algorithm revisited[C]. Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation, New York, USA, 2013: 291-298.
[11]
Eder C and Roune B H. Signature rewriting in Gröbner basis computation[C]. Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation, New York, USA, 2013: 331-338.
[12]
Huang Lei. A new conception for computing Gröbner basis and its applications[OL]. http://arxiv.org/abs/1012.5425. 2010.
[13]
Eder C. An analysis of inhomogeneous signature-based Gröbner basis computations[J]. Journal of Symbolic Computation, 2013, 59(0): 21-35.
[14]
Ding Jin-tai, Cabarcas D, Schmidt D, et al.. Mutant Gröbner basis algorithm[C]. Proceedings of the 1st International Conference on Symbolic Computation and Cryptography, Beijing, China, 2008: 23-32.