On The Criteria Of The F5 Algorithm
arXiv:0804.2033
Abstract
Faugere's F5 algorithm is one of the fastest known algorithms for the computation of Grobner bases. So far only the F5 Criterion is proved, whereas the second powerful criterion, the Rewritten Criterion, is not understood very well until now. We give a proof of both, the F5 Criterion and the Rewritten Criterion showing their connection to syzygies, i.e. the relations between the S-Polynomials to be investigated by the algorithm. Using the example of a Grobner basis computation stated in Faugere's F5 paper we show how the criteria work, and discuss the possibility of improving the F5 Criterion. An introduction to a SINGULAR implementation of F5 is given in the end.
1 new citation, new introduction, appendix about SINGULAR implementation
Cited by in corpus (6)
- A Generalized Criterion for Signature Related Gröbner Basis Algorithms
- A survey on signature-based Gröbner basis computations
- A New Proof for the Correctness of F5 (F5-Like) Algorithm
- Solving Detachability Problem for the Polynomial Ring by Signature-based Groebner Basis Algorithms
- A Generalized Criterion for Signature-based Algorithms to Compute Gröbner Bases
- The F5 Algorithm in Buchberger's Style