On The Criteria Of The F5 Algorithm

arXiv0804.2033MaRDI QIDQ6209130FDOQ6209130

Publication date: 12 April 2008

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.

This page was built for publication: On The Criteria Of The F5 Algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6209130)