A Modular Design and Implementation of Buchberger's Algorithm

Master's project presentation

Jennifer de Kleine, SFU



Buchberger's algorithm is an algorithm to compute a Grobner basis of a
system of polynomials.  A Grobner basis for a system of non-linear
polynomial equations is the analogue of row Echelon form for a linear
system of equations. One difficulty that arises in computing Grobner bases
over the rationals is coefficient blow-up in the intermediate computations.
One approach to dealing with this problem is to use a modular method.

The goal of this project is to design and implement a data structure that
supports an efficient modular implementation of Buchberger's algorithm.
The idea is to compute a Grobner basis modulo batches of primes and then
to reconstruct the rational answer using Chinese remaindering and rational
reconstruction.  The reason to compute modulo batches of primes is twofold.
Firstly, to speed up the overall computation, by amortizing the monomial
overhead across the batch of primes; and secondly to identify with high
probability primes which cannot be used.