##
**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.

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) |

PDF
BibTeX
XML
Cite

\textit{J.-C. Faugère}, J. Pure Appl. Algebra 139, No. 1--3, 61--88 (1999; Zbl 0930.68174)

Full Text:
DOI

### 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 |

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.