Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleThe F5 criterion revised
Author(s) Alberto Arri, John Perry
TypeArticle in Journal
AbstractThe purpose of this work is to generalize part of the theory behind Faugère’s “F5” algorithm. This is one of the fastest known algorithms to compute a Gröbner basis of a polynomial ideal I generated by polynomials f_1, … , f_m . A major reason for this is what Faugère called the algorithm’s “new” criterion, and we call “the F5 criterion”; it provides a sufficient condition for a set of polynomials G to be a Gröbner basis. However, the F5 algorithm is difficult to grasp, and there are unresolved questions regarding its termination. This paper introduces some new concepts that place the criterion in a more general setting: S -Gröbner bases and primitive S -irreducible polynomials. We use these to propose a new, simple algorithm based on a revised F5 criterion. The new concepts also enable us to remove various restrictions, such as proving termination without the requirement that f_1, … , f_m be a regular sequence.
KeywordsF5, Gröbner bases, Syzygies
URL http://www.sciencedirect.com/science/article/pii/S0747717111000642
JournalJournal of Symbolic Computation
Pages1017 - 1029
Translation No
Refereed No