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

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.


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


FGb; Gb; Maple; symrcm; IML++; Magma
Full Text: DOI


[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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.