Document Type
Article
Publication Date
9-1-2011
Department
Mathematics
School
Mathematics and Natural Sciences
Abstract
The purpose of this work is to generalize part of the theory behind Faugere'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 f1,…,fm. A major reason for this is what Faugere called the algorithm's "new" criterion, and we call "the F5 criterion": it provides a sufficient condition for a set of polynomialsGto 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 f1,…,fm be a regular sequence. (C) 2011 Elsevier Ltd. All rights reserved.
Publication Title
Journal of Symbolic Computation
Volume
46
Issue
9
First Page
1017
Last Page
1029
Recommended Citation
Arri, A.,
Perry, J. E.
(2011). The F5 Criterion Revised. Journal of Symbolic Computation, 46(9), 1017-1029.
Available at: https://aquila.usm.edu/fac_pubs/552
Comments
This is the peer reviewed version of the following article: "The F5 Criterion Revised," which has been published in final form at 10.1016/j.jsc.2011.05.004.