A modular method for Gröbner-basis construction over \(\mathbb{Q}\) and solving system of algebraic equations. (English) Zbl 0757.13012

Sasaki, Tateaki; Takeshima, Taku

J. Inf. Process. 12, No. 4, 371-379 (1989).

The Gröbner-basis of a polynomial ideal is currently one of the most important notations in algebraic computation. In this paper, the authors propose a complete modular method based on the Chinese remainder theorem. In their method, they do not check the luckiness of primes but check the unluckiness and finally they check the correctness of the basis constructed. In addition to this theoretical aspect, their algorithm seems to be quite useful because of its high efficiency.
In section 2, the authors summarize necessary notations and theorems on Gröbner-bases. Calculating a Gröbner-basis with special term ordering is directly related with solving a system of algebraic equations, and the authors also explain the Gröbner basis method for solving a system of algebraic equations. — In section 3, they consider the use of the Chinese remainder theorem to the Gröbner-basis construction. In particular, they discuss the treatment of “unlucky” primes. — In section 4, they present a probabilistic algorithm, prove its termination property, and discuss the probabilistic nature. A complete algorithm is presented in section 5, as well as improvements of the algorithm. Section 6 describes some empirical studies.

Reviewer: Y.Kuo (Knoxville)

MSC:

13P10	Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
12E12	Equations in general fields
11A07	Congruences; primitive roots; residue systems

Keywords:

Gröbner-basis of a polynomial ideal; modular method; Chinese remainder theorem; probabilistic algorithm