On modular computation of standard basis. (English) Zbl 1199.13032

Pfister, Gerhard

An. Științ. Univ. “Ovidius” Constanța, Ser. Mat. 15, No. 1, 129-138 (2007).

The computation of standard bases in a polynomial ring over \({\mathbb Q}\) is much more difficult than in a polynomial ring over a finite field \({\mathbb F}_p\) due to the enormous growth of the coefficients. The author proposes the following method. Let \(I \subseteq {\mathbb Q}[x_1, \dots, x_n]\) be an ideal, \(I_0\) its contraction to polynomials over \(\mathbb Z\) and \(I_p\) the extension of \(I_0\) to polynomials over \({\mathbb F}_p\). A prime \(p\) is called lucky if the minimal generating set of leading monomials of \(I\) and \(I_p\) are equal. Lucky primes can be computed looking the coefficients of the Hilbert function (in case of \(I\) been homogeneous) or the Hilbert–Samuel function (in case of a local ordering). For a given ideal \(I\) a big enough set of lucky primes is computed with its corresponding standard bases \(M_p\). Then they are lifted to a system of polynomials \(M\) using the Chinese remainder theorem and Farey fractions. If \(M\) is an standard basis for the given ideal then the process is finished, else the lucky primes are completed or even changed.
The author provides a table of timings to show that the modular algorithm is faster than the classical one.

Reviewer: F. J. Lobillo (Granada)

MSC:

13P10

Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)

Keywords:

standard bases; Gröbner bases; modular methods

Software:

SINGULAR