Faster Grobner Basis Computation

Jennifer de Kleine, SFU



We have done a modular design and implementation of Buchberger's
algorithm in Maple V Release 5.  In our method we compute Grobner
bases modulo batches of primes and then reconstruct the rational
answer using Chinese remaindering and rational reconstruction.

The bottleneck of this method is the division algorithm, in particular
the monomial arithmetic and vector operations in Zp_1 x ... x Zp_b.
We have now coded these critical operations in C and have linked the
external C subroutines to Maple.  In our polynomial representation we
store the coefficients in a 2-dimensional array of hardware floats and
the monomial exponent vectors in a 2-dimensional array of integers.
We are using 8 decimal digit primes and the modular arithmetic is done
using floating point arithmetic.  We have achieved significant
run-time improvements.