|Title||Slimgb: Gr\"obner bases with slim polynomials.|
|Author(s)|| Michael Brickenstein|
|Type||Article in Journal|
|Abstract||This paper introduces a variation of Buchbergers’s algorithm for computing Gröbner bases in order to avoid intermediate coefficient swell. It is designed to keep coefficients small and polynomials short during the computation. This pays off in computation time as well as memory usage.|
One of the newly introduced concepts is a weighted length of a polynomial, being a combination of the number of terms, the ecart and the coefficient size and may depend on the ground field and the monomial ordering. Further key features of the algorithm are parallel reductions, exchanging members of the generating system for shorter intermediate results and an extended version of the product criterion.
The algorithm is very flexible, the strategy is controlled by a single function which calculates the weighted length of a polynomial. All components of the algorithm depend on this function, hence one can easily customize the whole algorithm to fit the needs of specific problems by adjusting the weighted length.
The algorithm—called “slimgb”—is easy to implement in a standard Gröbner basis environment, as usual polynomial data structures are used.
|Keywords|| Gröbner basis, Buchberger algorithm |
|Journal||Rev. Mat. Complut.|
|Publisher||Springer, Milan; Universidad Complutense, Facultad de Matem|