Slimgb: Gröbner bases with slim polynomials (Q1958670): Difference between revisions

A modification of Buchberger's algorithm to compute Gröbner bases is presented in order to avoid intermediate coefficient swell. The aim is to keep polynomials short and coefficients small during the computation. One of the basic ideas is the concept of a weighted length of a polynomial (a suitable combination of the number of terms of the polynomial, its ecart and the coefficient size). Polynomials of shortest length are used in the reduction process, members of the actual Gröbner basis will be exchanged by shorter intermediate results if possible. This modification of Buchberger's algorithm, called \texttt{slimbg}, is implemented in the computer algebra system \texttt{Singular}. Experiments show (timings are given in the paper) that the algorithm for many examples is much more efficient than the ``ordinary'' Gröbner basis algorithm.