×

Efficient computation of zero-dimensional Gröbner bases by change of ordering. (English) Zbl 0805.13007

Gröbner bases are a useful tool for explicit computations in polynomial rings. Given a field \(K\), the polynomial ring \(K[X] = K[X_ 1, \dots, X_ n]\), an ideal \(I \subset K[X]\), and a total order (called a term order) on the semigroup of monomials such that 1 is the smallest element the Buchberger algorithm constructs a Gröbner basis of \(I\). In general different term orders yield different Gröbner bases. Once a Gröbner basis is known many computational problems (such as the ideal membership problem) can be solved. It is known that the choice of the term order greatly influences the performance of the Buchberger algorithm. The idea pursued in the present paper is first to determine a Gröbner basis with respect to a term order with low complexity and afterwards to translate this Gröbner basis into a Gröbner basis with respect to another term order. For zero-dimensional ideals an algorithm to this effect is presented. Complexity and examples are discussed.

MSC:

13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
68W30 Symbolic computation and algebraic computation
PDFBibTeX XMLCite
Full Text: DOI