Title

F5C: A Variant of Faugere's F5 Algorithm With Reduced Gröbner Bases

Document Type

Article

Publication Date

12-1-2010

Department

Mathematics

Abstract

The F5 algorithm for computing Gröbner 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.

Publication Title

Journal of Symbolic Computation

Volume

45

Issue

12

First Page

1442

Last Page

1458