Imperial Undergraduate Mathematics Colloquium: Gröbner bases, Buchberger’s algorithm and Faugère’s F4 algorithm
Date:
Talk about my Bachelor project. A Gröbner basis is a subset of a polynomial ideal with desirable algorithmic properties. Every set of polynomials can be transformed into a Gröbner basis through a process that generalises Gaussian elimination for solving linear systems of equations as well as the Euclidean algorithm for computing the greatest common divisor of two univariate polynomials. Introduced in Bruno Buchberger’s 1965 dissertation, the ideas behind Gröbner bases date back to earlier sources, including a paper written in 1900 by the invariant theorist Paul Gordan. Buchberger named his method after his advisor, Wolfgang Gröbner, and devised an algorithm to compute a Gröbner basis from any generating set of an ideal I: this is what is now known as Buchberger’s algorithm. However, even the best implementations of classical Buchberger algorithms do not succeed in computing Gröbner bases for complicated problems. Major improvements are due to Jean-Charles Faugère, who introduced the F4 algorithm in 1999 and the F5 algorithm in 2002. The idea of the F4 algorithm remains similar to Buchberger’s original algorithm —the novelty is the reductions of multiple S-pairs at once. F5 uses a whole new approach with the idea of signature reductions.