LEA
Fakultät für Informatik der Technischen Universität München
Lehrstuhl für Effiziente Algorithmen
Postadresse: 80290 München; Hausadresse: Arcisstr.21, 80333 München

Exponential space computation of Gröbner bases

Klaus Kühnle and Ernst W. Mayr

Short Abstract

Given a polynomial ideal and a term order, there is a unique reduced Gröbner basis and, for each polynomial, a unique normal form, namely the smallest (w.r.t. the term order) polynomial in the same coset. We consider the problem of finding this normal form for any given polynomial, without prior computation of the Gröbner basis. This is done by transforming a representation of the normal form into a system of linear equations and solving this system. Using the ability to find normal forms, we show how to obtain the Gröbner basis in exponential space.

Long Abstract

Let Q[x1,...,xn] be the polynomial ring in the indeterminates x1,...,xn over the rationals and let some term order (i.e. a total order on the power products extending the divisibility relation and respecting multiplication) be given. We will consider an ideal in the polynomial ring Q[x1,...,xn]. With respect to this ideal and the given term order we then have, for any polynomial, a unique normal form, namely the smallest (w.r.t. the term order) monic polynomial in the same coset (there is a canonical extension of the term order to monic polynomials).

We consider the problem of finding this normal form for any given polynomial. As a solution, we will represent the difference of the given polynomial and its normal form as a linear combination of the ideal generators, transform this representation into a system of linear equations and solve this system. This is possible because we can bound the degrees of the normal form and of the polynomials being the coefficients in the linear combination by virtue of two already known degree bounds (Dubé 1990, Hermann 1926).

As an application of this normal form calculation we will compute the unique reduced Gröbner basis of the given ideal with respect to the given term order. A Gröbner basis is a set of generators that allows normal forms to be calculated by a simple division algorithm. In such a division algorithm the given polynomial is repeatedly replaced by its remainder upon division by some generator as long as this is possible. It is a characteristic property of Gröbner bases that this division algorithm will in any case yield the normal form of the given polynomial.

The computation of the Gröbner basis runs as follows: We will enumerate all terms up to the known bound (Dubé 1990) on the degrees of the polynomials in the Gröbner basis and calculate their normal forms. If a term is not irreducible (i.e. is not equal to its normal form) but all its divisors are, then we will add the difference of this term and its normal form to the Gröbner basis.