A new efficient algorithm for computing Gröbner bases \((F_4)\) (Q1295781)

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.