zbMATH — the first resource for mathematics

Efficiently computing minimal sets of critical pairs. (English) Zbl 1137.13315
Summary: In the computation of a Gröbner basis using Buchberger’s algorithm, a key issue for improving the efficiency is to produce techniques for avoiding as many unnecessary critical pairs as possible. A good solution would be to avoid all non-minimal critical pairs, and hence to process only a minimal set of generators of the module generated by the critical syzygies. In this paper we show how to obtain that desired solution in the homogeneous case while retaining the same efficiency as with the classical implementation. As a consequence, we get a new optimized Buchberger algorithm.

13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
14Q20 Effectivity, complexity and computational aspects of algebraic geometry
68W30 Symbolic computation and algebraic computation
Full Text: DOI
[1] Buchberger, B., 1965. Ein Algorithmus zum Auffinden der Basiselemente des Restklassenrings nach einem nulldimensionalen Polynomideal. Ph.D. Thesis, Universität Innsbruck · Zbl 1245.13020
[2] Buchberger, B., A criterion for detecting unnecessary reductions in the construction of Groebner bases, (), 3-21
[3] Buchberger, B., Groebner bases: an algorithmic method in polynomial ideal theory, (), 184-232
[4] Caboara, M.; Kreuzer, M.; Robbiano, L., Minimal sets of critical pairs, (), 390-404 · Zbl 1057.68136
[5] Cocoa, 2001. A system for doing computations in commutative algebra, Available via anonymous ftp from
[6] Faugère, J.C., A new efficient algorithm for computing Gröbner bases without reduction to zero (F5), (), 75-83 · Zbl 1072.68664
[7] Gebauer, R.; Möller, H.M., On an installation of buchberger’s algorithm, J. symbolic comput., 6, 257-286, (1987) · Zbl 0675.13013
[8] Kreuzer, M.; Robbiano, L., Computational commutative algebra 1, (2000), Springer Heidelberg · Zbl 0956.13008
[9] Kreuzer M., Robbiano L. Computational Commutative Algebra 2. Springer, Heidelberg (in preparation) · Zbl 1090.13021
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.