Document Type

Article

Publication Date

12-1-2010

Department

Mathematics

School

Mathematics and Natural Sciences

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.

Comments

This is the peer reviewed version of the following article: "F5C: A variant of Faugère’s F5 algorithm with reduced Gröbner bases," which has been published in final form at 10.1016/j.jsc.2010.06.019.

Publication Title

Journal of Symbolic Computation

Volume

45

Issue

12

First Page

1442

Last Page

1458

Download

Find in your library

Share

COinS