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.