Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleSlimgb: Gr\"obner bases with slim polynomials.
Author(s) Michael Brickenstein
TypeArticle in Journal
AbstractThis 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
ISSN1139-1138; 1988-2807/e
URL http://link.springer.com/article/10.1007%2Fs13163-009-0020-0
JournalRev. Mat. Complut.
PublisherSpringer, Milan; Universidad Complutense, Facultad de Matem
Translation No
Refereed No