A new efficient algorithm for computing Gröbner bases \((F_4)\). (English) Zbl 0930.68174

Faugère, Jean-Charles

J. Pure Appl. Algebra 139, No. 1-3, 61-88 (1999).

The first part of the paper contains the description and theoretical foundations of a new, implementation oriented algorithmic method for the computation of Gröbner bases of polynomial ideals.
Degree-truncated Gröbner basis computations, sparse linear algebra routines and parallel computing are used in order to speed up the classical Buchberger algorithm (in the past these tools were only applied to the theoretical worst case complexity analysis of this algorithm).
The new procedure combines term rewriting with linear algebra. Its main feature consists in the simultaneous reduction of several polynomials modulo a precomputed list of them. This is done in a parallel way, using sparse linear algebra routines. This aspect of massive parallel computation distinguishes the new procedure from the classical Buchberger algorithm.
The paper ends with a comparison of the implemented version of the new algorithm (the program FGb) with its forerunner Gb and some of its competitors. The author claims that the program FGb behaves almost optimally with respect to time complexity. Time seems to be almost proportional to the (objective) output size.

Reviewer: Joos Heintz (Buenos Aires)

MSC:

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

Keywords:

computation of Gröbner bases of polynomial ideals; Buchberger algorithm

Software:

FGb; Gb; Maple; symrcm; IML++; Magma

References:

[13]	Dixon, J. D., Exact solution of linear equations using \(p\)-adic expansions, Numer. Math., 40, 137-141 (1982) · Zbl 0492.65016
[15]	Duff, I. S.; Reid, J. K., The multifrontal solution of unsymmetric sets of linear equations, SIAM J. Sci. Statist. Comput., 5, 3, 633-641 (1984) · Zbl 0557.65017