The F5 criterion revised
Alberto Arri · ACM communications in computer algebra · 2009
The purpose of this work is to generalize the theory behind the "F5" algorithm presented by J.C. Faugère in [3] and its matrix variant described by M. Bardet in [1]. The F5 algorithm is an algorithm which computes the Gröbner basis of a given polynomial ideal I from its generators F = ( f 1 , ... , fm ). Faugère's main idea is to consider the expression of an element p ∈ I in terms of the generators, p = ∏ h i f i , and keep explicitly track of the leading term S ( p ) of the vector ( h 1 , ... , h m ), taken in its normal form with respect to the module of syzygies of F . We provide a novel rigorous proof of a more general criterion than the one stated by Faugère, which establishes when a set of polynomials G is a Gröbner basis by considering the values S ( g ) for all g ∈ G ; we further generalize our result by removing the requirement that the sequence f 1 , ... , f m is a regular sequence. The criterion itself is based on the knowledge of the module LT(Syz F ), we have however devised an algorithm which simultaneously computes (a subset of) LT(Syz F ) and a Gröbner basis of I . We had written a first prototypal implementation in C++ using CoCoAlib [2] and we are currently working on a new implementation of the algorithm again in C++ from scratch.