Bjarke Roune

The F4 Algorithm - Speeding Up Groebner Basis Computation Using Linear Algebra

Abstract: A major reason for the popularity of Gröbner bases is that they can be computed using Buchberger's algorithm. Even though its worst case complexity is doubly exponential, the Buchberger algorithm can compute Gröbner bases bases of many ideals of practical interest, and it has been radically improved in the last number of years.
This talk is about such an improved variant of the Buchberger algorithm called F4 (due to Faugere), which speeds up the reduction step in the Buchberger algorithm by exchanging multiple polynomial divisions for row-reduction of a single sparse matrix.

See the note accompanying the talk at

...Back to the IMA postdoc seminar page...