F5C: A variant of Faugere's F5 algorithm with reduced Grobner bases
The F5 algorithm for computing Grobner bases achieves a high level of efficiency through the careful analysis of signatures assigned to each computed polynomial. However, it computes and uses many polynomials that turn out to be redundant. Eliminating these redundant polynomials is a non-trivial task, because they correspond to signatures required for reduction. This paper revisits the theory underlying F5 and describes F5C, a new variant that prunes redundant polynomials, then re-computes signatures to preserve correctness. This strategy successfully reduces both overhead and execution time. (C) 2010 Elsevier Ltd. All rights reserved.
f5 reduced grobner bases buchberger's criteria