Efficiently Computing Minimal Sets of Critical Pairs

M. Caboara^{a,∗}, M. Kreuzer^{b}, L. Robbiano^{a}

aDepartment of Mathematics, University of Genoa, Italy

bFachbereich Mathematik, Universität Dortmund, Germany

Abstract

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.

Key words: Critical Pairs, Buchberger Algorithm

1 Introduction

Ever since practical implementations of Buchberger’s famous algorithm for computing Gröbner bases became feasible (Buchberger, 1965), it has been clear that, in order to improve the efficiency of this algorithm, one needs to avoid the treatment of as many critical pairs as possible. Buchberger (1979) studied this problem for the first time, and later in (Buchberger, 1985) and (Gebauer and Möller, 1987) his results were substantially improved and expanded. Nevertheless, Gebauer and Möller (1987) showed that their method did not always produce a minimal set of generators of the module generated by the critical syzygies. However, their method was very efficient and yielded an almost

∗ Corresponding author.

Email addresses: caboara@dima.unige.it (M. Caboara),

Martin.Kreuzer@mathematik.uni-dortmund.de (M. Kreuzer),
robbiano@dima.unige.it (L. Robbiano).

Preprint submitted to Journal of Symbolic Computation 14 January 2005

minimal set of critical pairs. Since then, many kinds of optimizations of Buchberger’s algorithm have been found, in particular by implementers of computer algebra systems. But the problem of efficiently minimalizing the critical pairs has gone largely unnoticed and seems to be overdue for a solution. Indeed, that is the main objective of this paper.

To achieve our goal, we proceed as follows. Foremost, we need a detailed understanding of the entire process of computing Gröbner bases, in particular in the homogeneous case. An algorithm for simultaneously computing a Gröbner basis and a minimal system of generators contained in it is fine-tuned when the input is a reduced Gröbner basis. Then this result is applied to critical syzygies, using the fact that we show how the old criteria M(i, j) and F (i, j) of (Gebauer and Möller, 1987) yield a reduced Gröbner basis of the module of syzygies of the leading terms. Besides, when applied to this special case, the algorithm admits many subtle optimizations. In the end, we really achieve the goal of minimalizing the critical pairs efficiently.

Now, why do we think that what we achieved is important?

The first reason is theoretical curiosity. It is common knowledge among the implementers of Buchberger’s algorithm that the criteria of Gebauer and Möller almost produce a minimal set of critical pairs. We wanted to see whether that vox populi is really true. Of course one could use a standard minimalization process to produce minimal sets of critical pairs, but this method could only handle small examples. Instead, we observed that, after applying two of the criteria of Gebauer and Möller, a reduced Gröbner basis of the module of syzygies of the leading terms is obtained. Then we were able to see the difference between the reduced Gröbner basis and a minimal set of generators of this module, and how this difference depends on the size of the example.

Another important reason is that we wanted to be able to compute a minimal set of generators of this module with the same efficiency as the usual application of the Gebauer-Möller criteria. And we wanted to do it while computing a Gröbner basis, so that we can replace the Gebauer-Möller criteria by our procedure. As we show in the last sections, we achieved this goal.

A third reason is that our results hold in full generality, namely for Gröbner bases of modules over positively (multi-) graded rings. Other optimizations of Buchberger’s algorithm, e.g. ideas using trivial syzygies (see for instance Faugere (2002)), do not hold in this generality. Moreover, we would like to point out that the pairs we discard are truly useless, whereas pairs between elements in a reduced Gröbner bases which reduce to zero can still be useful for the computation of syzygies.

Finally, the readers should know that the basic terminology is taken from the book of the second and third authors (Kreuzer and Robbiano, 2000).

2 Some Background Material

Since we are interested in optimizing Buchberger’s algorithm in the homogeneous case, we start by saying which gradings we consider. From now on let K be a field and P = K[x_{1}, …, x_{n}] a polynomial ring over K. Moreover, let W ∈ Mat_{m,n}(ℤ) be an m×n-matrix with integer entries. Then there exists exactly one ℤ^{m}-grading on P such that every term t = x_{1}^{α_{1}} ⋯ x_{n}^{α_{n}} is homogeneous of degree deg_{W} (t) = W · (α_{1}, …, α_{n})^{tr}. We say that P is (multi-) graded by W. The matrix W is called the degree matrix and its rows are called the weight vectors.

For instance, the grading on P given by W = (1, …, 1) is the standard grading. For every d ∈ ℤ^{m}, the homogeneous component of degree d of P is P_{W,d} = ⊕_{deg_{W} (t)=d} K · t. Given δ_{1}, …, δ_{r} ∈ ℤ^{m}, the graded free P -module F = ⊕_{i=1}^{r} P (−δ_{i}) inherits a ℤ^{m}-grading from P in the natural way. Again we say that F is graded by W.

In order to be able to use these gradings in our algorithms, we need some positivity assumptions.

Definition 1 Let P be graded by W, and let w_{1}, …, w_{m} be the rows of W.

a) The grading given by W is called weakly positive if there exist integers a_{1}, …, a_{m} such that a_{1}w_{1} + ⋯ + a_{m}w_{m} has all entries strictly positive.

b) The grading given by W is called positive if rk(W) = m, if no column of W is zero, and if the first non-zero entry in each column of W is positive.

Proposition 2 Let P be weakly positively graded by W, and let M be a finitely generated graded P -module.

a) We have P_{W,0} = K and dim_{K}(M_{W,d}) < ∞ for every d ∈ ℤ^{m}.

b) The graded version of Nakayama’s lemma holds: homogeneous elements v_{1}, …, v_{s} ∈ M generate the module M if and only if their residue classes \overline{v}_{1}, …, \overline{v}_{s} generate the K -vector space M/(x_{1}, …, x_{n})M. In particular, every homogeneous system of generators of M contains a minimal one, and all irredundant homogeneous systems of generators of M have the same number of elements which is denoted by μ(M).

The proof of this proposition uses standard computer algebra methods and is contained in (Kreuzer and Robbiano, in preparation). For practical computations we need the somewhat stronger notion of a positive grading. The usefulness of positive gradings is illustrated by the following characterizations.

Recall that a module ordering σ on the set of terms 𝕋^{n}⟨e_{1}, …, e_{r}⟩ of the graded free module F is called degree compatible or compatible with deg_{W} if the inequality deg_{W} (te_{i}) >_{Lex} deg_{W} (t′e_{j}) implies te_{i} >_{σ} t′e_{j} for all t, t′ ∈ 𝕋^{n} and all i, j ∈ {1, …, r}.

Proposition 3 Let P be graded by W, where W has ℤ-linearly independent rows and non-zero columns. Then the following conditions are equivalent.

a) The grading on P given by W is positive.

b) The restriction of Lex to the monoid Γ = {d ∈ ℤ^{m} | P_{W,d} ≠ 0} is a well-ordering, i.e. every non-empty subset of Γ has a minimal element with respect to Lex.

c) The restriction of Lex to the monoid Γ = {d ∈ ℤ^{m} | P_{W,d} ≠ 0} is a term ordering, i.e. every element d ∈ Γ satisfies d >_{Lex} 0.

d) There exists a term ordering τ on 𝕋^{n} which is compatible with deg_{W}.

e) There exists a module term ordering σ on 𝕋^{n}⟨e_{1}, …, e_{r}⟩ which is compatible with the grading given by W.

Again we refer to (Kreuzer and Robbiano, in preparation) for a proof of this proposition. As a consequence, it follows that positive gradings are weakly positive. Moreover, in a positively graded setting, we can prove the finiteness of various algorithms in the usual way, i.e. by using the fact that there is no infinite sequence of homogeneous elements of strictly decreasing degrees.

In the remaining part of this section, we use truncated Gröbner bases to prove two very important technical tools, namely Corollary 8 and Corollary 10. We shall from now on assume that P is positively graded by W ∈ Mat_{m,n}(ℤ). Moreover, we let δ_{1}, …, δ_{r} ∈ ℤ^{m}, we let M be a finitely generated graded submodule of the graded free P -module F = ⊕_{i=1}^{r} P (−δ_{i}), and we let σ be a module term ordering on 𝕋^{n}⟨e_{1}, …, e_{r}⟩, the set of terms in F.

The following notation will turn out to be convenient. Given a subset S of a graded P -module and d ∈ ℤ^{m}, we let S_{≤d} = {v ∈ S | v homogeneous, deg_{W} (v) ≤_{Lex} d} and S_{d} = {v ∈ S | v homogeneous, deg_{W} (v) = d}.

Definition 4 Assume that G = {g_{1}, …, g_{s}} is a homogeneous σ-Gröbner basis of M, and let d ∈ ℤ^{m}. Then the set G_{≤d} is called a d-truncated Gröbner basis of M, or a Gröbner basis of M which has been truncated in degree d.

For truncated Gröbner bases, we now prove a characterization which is analogous to the Buchberger criterion in the usual case. To this end, we need to explain what we mean by critical pairs and critical syzygies.

Given homogeneous elements g_{1}, …, g_{s} ∈ M \ {0}, we let d_{i} = deg_{W} (g_{i}) for i = 1, …, s, and we let F′ be the graded free P -module ⊕_{i=1}^{s} P (−d_{i}). The canonical basis of F′ will be denoted by {ε_{1}, …, ε_{s}}. Notice that we have deg_{W} (ε_{i}) = d_{i} for i = 1, …, s. Moreover, we write LM_{σ}(g_{i}) = c_{i}t_{i}e_{γ_{i}}, where c_{i} ∈ K \ {0}, where t_{i} ∈ 𝕋^{n}, and where γ_{i} ∈ {1, …, r}.

Definition 5 A pair (i, j) ∈ {1, …, s} such that 1 ≤ i < j ≤ s and γ_{i} = γ_{j} is called a critical pair of (g_{1}, …, g_{s}). The set of all critical pairs of (g_{,} …, g_{s}) is denoted by 𝔹. For every critical pair (i, j) ∈ 𝔹, the element σ_{ij} = \frac{lcm(t_{i},t_{j})}{c_{i}t_{i}} ε_{i} − \frac{lcm(t_{i},t_{j})}{c_{j}t_{j}} ε_{j} is a syzygy of the pair (LM_{σ}(g_{i}), LM_{σ}(g_{j})). It is called the critical syzygy associated to the critical pair (i, j). The set of all critical syzygies is denoted by Σ.

Clearly, a critical syzygy σ_{ij} is a homogeneous element of F′ whose degree is precisely deg_{W} (σ_{ij}) = deg_{W} (lcm(t_{i}, t_{j})) + δ_{γ_{i}}. This degree equals the degree of the corresponding S-vector S_{ij} = \frac{lcm(t_{i},t_{j})}{c_{i}t_{i}} g_{i} − \frac{lcm(t_{i},t_{j})}{c_{j}t_{j}} g_{j} in F.

For every critical pair (i, j) ∈ 𝔹, we call deg_{W} (σ_{ij}) the degree of the critical pair. Then it makes sense to consider the set 𝔹_{≤d} for every given d ∈ ℤ^{m}, and we observe that deg_{W} (σ_{ij}) ≥_{Lex} max{d_{i}, d_{j}} for all (i, j) ∈ 𝔹. Finally, we remind the reader that NR_{σ,G}(v) denotes normal remainder, i.e. the result of the division algorithm, as in (Kreuzer and Robbiano, 2000), Definition 1.6.7. At this point, we are ready to formulate and prove the following characterization of truncated Gröbner bases.

Proposition 6 (Characterization of Truncated Gröbner Bases) Let P be positively graded by W ∈ Mat_{m,n}(ℤ), let G = {g_{1}, …, g_{s}} be a set of non-zero homogeneous vectors which generates a graded submodule M of ⊕_{i=1}^{r} P (−δ_{i}), and let d ∈ ℤ^{m}. Then the following conditions are equivalent.

a) The set G_{≤d} is a d-truncated σ-Gröbner basis of M.

b) For every homogeneous element v ∈ M_{≤d} \ {0}, we have the relation LT_{σ}(v) ∈ ⟨LT_{σ}(g) | g ∈ G_{≤d}⟩.

c) For all pairs (i, j) ∈ 𝔹_{≤d}, we have NR_{σ,G_{≤d}}(S_{ij}) = 0, where G_{≤d} is the tuple obtained from G = (g_{1}, …, g_{s}) by deleting the elements of degree greater than d.

Proof. Without loss of generality, we may assume that G_{≤d} = {g_{1}, …, g_{s′}} for some s′ ≤ s. It is clear that a) implies both b) and c). Now we show that b) implies a). By the assumption, we can find terms t′_{s′+1}, …, t′_{s′′} of degree greater than d such that the set {LT_{σ}(g_{1}), …, LT_{σ}(g_{s′})} ∪ {t′_{s′+1}, …, t′_{s′′}} is a system of generators of LT_{σ}(M). We choose homogeneous elements h_{s′+1}, …, h_{s′′} in M such that LT_{σ}(h_{i}) = t′_{i} for i = s′ + 1, …, s′′. Then the set {g_{1}, …, g_{s′}, h_{s′+1}, …, h_{s′′}} is a homogeneous σ-Gröbner basis of M with truncation G_{≤d}.

It remains to prove that c) implies b). Let v ∈ M_{≤d} be a homogeneous non-zero element. Since {g_{1}, …, g_{s′}} generates ⟨M_{≤d}⟩, we can represent v as v = ∑_{i=1}^{s′} f_{i}g_{i}, where f_{i} is homogeneous of degree deg_{W} (v)−deg_{W} (g_{i}) ≤_{Lex} d. In order to prove LT_{σ}(v) ∈ ⟨LT_{σ}(g_{1}), …, LT_{σ}(g_{s′})⟩, it is enough to proceed as in the proof of Proposition 2.3.12 of (Kreuzer and Robbiano, 2000), replacing G by G_{≤d}. ⊓ ⊔

This characterization has several useful applications.

Corollary 7 Let G = {g_{1}, …, g_{s}} be a homogeneous σ-Gröbner basis of the module M, and let d ∈ ℤ^{m}. Then G_{≤d} is a d-truncated σ-Gröbner basis of the module ⟨M_{≤d}⟩.

Proof. Since G is a set of generators of M, the set G_{≤d} generates the module ⟨M_{≤d}⟩. From Buchberger’s Criterion we know that NR_{σ,G}(S_{ij}) = 0, for all pairs (i, j) ∈ 𝔹. If we have deg_{W} (S_{ij}) ≤_{Lex} d here, the elements of G involved in the reduction steps S_{ij} ⟶^{G} 0 all have degrees less than or equal to d. Hence we see that NR_{σ,G_{≤d}}(S_{ij}) = 0, and the proposition yields the claim. ⊓ ⊔

Corollary 8 Let d ∈ ℤ^{m}, let the elements of the tuple G = (g_{1}, …, g_{s}) form a d-truncated σ-Gröbner basis of M, and let g_{s+1} ∈ F be a homogeneous element of degree d such that LT_{σ}(g_{s+1}) ∉ ⟨LT_{σ}(g_{1}), …, LT_{σ}(g_{s})⟩. Then {g_{1}, …, g_{s+1}} is a d-truncated Gröbner basis of M + ⟨g_{s+1}⟩.

Proof. In order to prove the claim, we check condition c) of the proposition. For 1 ≤ i < j ≤ s such that deg_{W} (S_{ij}) ≤_{Lex} d, we have NR_{σ,G}(S_{ij}) = 0 by the assumption and by Proposition 6. For i ∈ {1, …, s} such that deg_{W} (S_{i s+1}) = d, the fact that the pair (i, s + 1) has degree d implies that LT_{σ}(g_{s+1}) is a multiple of LT_{σ}(g_{i}), in contradiction to the hypothesis. ⊓ ⊔

In the last part of this section, we prove an analogue of the preceding corollary for minimal generators. Recall that Proposition 2.b guarantees that all minimal systems of generators have the same length in the positively graded situation.

Proposition 9 Let P be positively graded by W ∈ Mat_{m,n}(ℤ), let M be a graded P -module generated by homogeneous elements {g_{1}, …, g_{s}}, and assume that deg_{W} (g_{1}) ≤_{Lex} deg_{W} (g_{2}) ≤_{Lex} ⋯ ≤_{Lex} deg_{W} (g_{s}).

a) The set {g_{1}, …, g_{s}} is a minimal system of generators of M if and only if we have g_{i} ∉ ⟨g_{1}, …, g_{i−1}⟩ for i = 1, …, s.

b) The set {g_{i} | i ∈ {1, …, s}, g_{i} ∉ ⟨g_{1}, …, g_{i−1}⟩} is a minimal system of generators of M.

Proof. First we prove a). If {g_{1}, …, g_{s}} is a minimal set of generators of M, then no relation of type g_{i} ∈ ⟨g_{1}, …, g_{i−1}⟩ holds, since otherwise we would have M = ⟨g_{1}, …, g_{i−1}, g_{i+1}, …, g_{s}⟩. Conversely, if {g_{1}, …, g_{s}} is not a minimal set of generators of M, then there exists an index i ∈ {1, …, s} such that g_{i} ∈ ⟨g_{1}, …, g_{i−1}, g_{i+1}, …, g_{s}⟩. Using Corollary 1.7.11 of (Kreuzer and Robbiano, 2000), we obtain a representation g_{i} = ∑_{j≠i} f_{j}g_{j}, where f_{j} ∈ P is homogeneous of degree deg_{W} (g_{i})−deg_{W} (g_{j}) for j ∈ {1, …, i−1, i+1, …, s}.

Since deg_{W} (f_{j}) ≥_{Lex} 0 for f_{j} ≠ 0, we see that deg_{W} (g_{i}) <_{Lex} deg_{W} (g_{j}) implies f_{j} = 0. Thus there are two possibilities. Either we have deg_{W} (g_{i}) >_{Lex} deg_{W} (g_{j}) for all j such that f_{j} ≠ 0 or there exist some indices j such that deg_{W} (g_{j}) = deg_{W} (g_{i}). In the first case, those indices j satisfy j < i by the assumption that the multidegrees of g_{1}, …, g_{s} are ordered increasingly, and therefore we get g_{i} ∈ ⟨g_{1}, …, g_{i−1}⟩. In the second case, the f_{j} corresponding to those indices j are in K \{0}. Let j_{max} = max{j ∈ {1, …, s} | f_{j} ∈ K \{0}}. We get the relation g_{j_{max}} ∈ ⟨g_{1}, …, g_{j_{max}−1}⟩. In both cases, we arrive at a contradiction to our hypothesis.

Now let us show b). The set S = {g_{i} | i ∈ {1, …, s}, g_{i} ∉ ⟨g_{1}, …, g_{i−1}⟩} is a system of generators of M, because an element g_{i} such that g_{i} ∈ ⟨g_{1}, …, g_{i−1}⟩ is also contained in ⟨g_{j} ∈ S | 1 ≤ j ≤ i − 1⟩. The fact that this system of generators is minimal follows from a). ⊓ ⊔

The following version is an immediate consequence of part a) of the proposition.

Corollary 10 Let N be a graded P -module, let M be a submodule of N, let {g_{1}, …, g_{s}} be a minimal homogeneous system of generators of M, and let g_{s+1} ∈ N \ M be a homogeneous vector whose degree satisfies the inequality deg_{W} (g_{s+1}) ≥_{Lex} max{deg_{W} (g_{i}) | i = 1, …, s}. Then {g_{1}, …, g_{s+1}} is a minimal system of generators of the module M + ⟨g_{s+1}⟩. In particular, we have μ(M + ⟨g_{s+1}⟩) = μ(M) + 1.

3 Minimal Generators in a Reduced Gröbner Basis

From here on we use the following assumptions. Let K be a field, and let P = K[x_{1}, …, x_{n}] be a polynomial ring over K which is positively graded by a matrix W ∈ Mat_{m,n}(ℤ). Then let r ≥ 1, let δ_{1}, …, δ_{r} ∈ ℤ^{m}, and let M be a graded submodule of F = ⊕_{i=1}^{r} P (−δ_{i}) which is generated by a set of non-zero homogeneous vectors {v_{1}, …, v_{s}}. Furthermore, we choose a module term ordering σ on the monomodule of terms 𝕋^{n}⟨e_{1}, …, e_{r}⟩ in F, and we let V = (v_{1}, …, v_{s}).

Our first goal is to describe an algorithm which computes a homogeneous σ-Gröbner basis of M degree-by-degree and a variant of this algorithm which also yields a minimal system of generators of M contained in V. This part is classical and more or less “well-known”. Then we make good use of it in Theorem 15 for minimalizing reduced Gröbner bases.

To ease the notation, we shall use the following convention: whenever a vector g_{i} appears, we write LM_{σ}(g_{i}) = c_{i}t_{i}e_{γ_{i}}, where c_{i} ∈ K \{0}, where t_{i} ∈ 𝕋^{n}, and where γ_{i} ∈ {1, …, r}. For two indices i, j such that γ_{i} = γ_{j}, we let σ_{ij} = \frac{lcm(t_{i},t_{j})}{c_{i}t_{i}} ε_{i} − \frac{lcm(t_{i},t_{j})}{c_{j}t_{j}} ε_{j} and S_{ij} = \frac{lcm(t_{i},t_{j})}{c_{i}t_{i}} g_{i} − \frac{lcm(t_{i},t_{j})}{c_{j}t_{j}} g_{j}.

Theorem 11 (The Homogeneous Buchberger Algorithm) In the above situation, consider the following instructions.

1) Let B = ∅, W = V, G = ∅, and let s′ = 0.

2) Let d be the smallest degree with respect to Lex of an element of B or of W. Form B_{d} and W_{d}, and delete their entries from B and W, respectively.

3) If B_{d} = ∅, continue with step 6). Otherwise, chose a pair (i, j) ∈ B_{d} and remove it from B_{d}.

4) Compute the S-vector S_{ij} and its normal remainder S′_{ij} = NR_{σ,G}(S_{ij}). If S′_{ij} = 0, continue with step 3).

5) Increase s′ by one, append g_{s′} = S′_{ij} to the tuple G, and append the set {(i, s′) | 1 ≤ i < s′, γ_{i} = γ_{s′}} to the set B. Continue with step 3).

6) If W_{d} = ∅, continue with step 9). Otherwise, choose a vector v ∈ W_{d} and remove it from W_{d}.

7) Compute v′ = NR_{σ,G}(v). If v′ = 0, continue with step 6).

8) Increase s′ by one, append g_{s′} = v′ to the tuple G, and append the set {(i, s′) | 1 ≤ i < s′, γ_{i} = γ_{s′}} to the set B. Continue with step 6).

9) If B = ∅ and W = ∅, return the tuple G and stop. Otherwise, continue with step 2).

This is an algorithm which returns a σ-Gröbner basis G of M, where the tuple G consists of homogeneous vectors having non-decreasing multidegrees.

The proof of this theorem is standard Computer Algebra and is for instance contained in (Kreuzer and Robbiano, in preparation).

Remark 12 Let us add some observations about this algorithm.

a) If we interrupt its execution after some degree d_{0} is finished, the tuple G is a d_{0}-truncated Gröbner basis of M. Consequently, we can compute truncated Gröbner bases efficiently. Moreover, in this case it suffices to append only the pairs {(i, s′) | 1 ≤ i < s′, γ_{i} = γ_{s′}, deg_{W} (σ_{is′}) ≤_{Lex} d_{0}} to the set B in steps 5) and 8). The reason is that pairs of higher degree are never processed anyway, since we stop the computation after finishing

degree d_{0}.

b) It is not required that σ is a degree compatible module term ordering. The reason is that, during the computation of the Gröbner basis, only comparisons of terms in the support of a homogeneous vector are performed. Thus these terms have the same degree, and it does not matter whether σ is degree compatible or not.

c) The Homogeneous Buchberger Algorithm can also be viewed as a special version of the usual Buchberger Algorithm where we use a suitable selection strategy.

The following variant of the Homogeneous Buchberger Algorithm computes a minimal system of generators of M contained in the given set of generators while computing a Gröbner basis. It provides an efficient method for finding minimal systems of generators.

Corollary 13 (Buchberger Algorithm with Minimalization) In the situation of the theorem, consider the following instructions.

1’) Let B = ∅, W = V, G = ∅, s′ = 0, and V_{min} = ∅.

2) Let d be the smallest degree with respect to Lex of an element of B or of W. Form B_{d} and W_{d}, and delete their entries from B and W, respectively.

3) If B_{d} = ∅, continue with step 6). Otherwise, chose a pair (i, j) ∈ B_{d} and remove it from B_{d}.

4) Compute the S-vector S_{ij} and its normal remainder S′_{ij} = NR_{σ,G}(S_{ij}). If S′_{ij} = 0, continue with step 3).

5) Increase s′ by one, append g_{s′} = S′_{ij} to the tuple G, and append the set {(i, s′) | 1 ≤ i < s′, γ_{i} = γ_{s′}} to the set B. Continue with step 3).

6) If W_{d} = ∅, continue with step 9). Otherwise, choose a vector v ∈ W_{d} and remove it from W_{d}.

7) Compute v′ = NR_{σ,G}(v). If v′ = 0, continue with step 6). 8’) Increase s′ by one, append g_{s′} = v′ to the tuple G, append v to the

tuple V_{min}, and append {(i, s′) | 1 ≤ i < s′, γ_{i} = γ_{s′}} to the set B. Continue with step 6).

9’) If B = ∅ and W = ∅, return the pair (G, V_{min}) and stop. Otherwise, continue with step 2).

This is an algorithm which returns a pair (G, V_{min}) such that G is a tuple of homogeneous vectors which are a σ-Gröbner basis of M, and V_{min} is a subtuple of V of homogeneous vectors which are a minimal system of generators of M.

Proof. In view of the theorem, we only have to show that the elements in V_{min} are a minimal set of generators of M. Since the algorithm is finite, it operates in only finitely many degrees d. Therefore it suffices to prove by induction on d that V_{min} contains a minimal system of generators of ⟨M_{≤d}⟩ after the algorithm has finished working on elements of degree d.

This is clearly the case at the outset. Suppose it is true for the last degree treated before d. Inductively, we can show that the elements of G continue to be contained in the module ⟨M_{<d}⟩ while we are looping through steps 3), 4), and 5) of the algorithm. Namely, every time an element of the form NF_{σ,G}(S_{ij}) is added to G, it is clearly contained in the module generated by the previous elements of G. Furthermore, by part a) of the remark following Theorem 11, the elements of the tuple G form a d-truncated Gröbner basis of ⟨M_{<d}⟩ after we have finished looping through steps 3), 4), and 5), i.e. when we have treated all pairs of degree d.

Now let W_{d} = (w_{1}, …, w_{ℓ}), and let the numbering of these vectors correspond to the order in which they are chosen in step 6). We show that, for each application of steps 6), 7), and 8’), the elements of V_{min} continue to be a minimal system of generators of the module they generate, and that this module always agrees with the one generated by the elements of G. Furthermore, the elements of G are always a d-truncated σ-Gröbner basis of that module.

When a new vector v = w_{i} is chosen in step 6), there are two possibilities. If v′ = 0 in step 7), then v is already contained in the module M′ generated by the elements of V_{min}. Otherwise, the vector v′ is not contained in M′, since the elements of G are a d-truncated σ-Gröbner basis and we can apply the Submodule Membership Test (see (Kreuzer and Robbiano, 2000), Proposition 2.4.10.a). In that case, the elements of V_{min}, together with v, form a minimal system of generators of the module M′ + ⟨v⟩ = M′ + ⟨v′⟩ by Corollary 10. Moreover, the elements of G, together with v′, form a d-truncated σ-Gröbner basis of M′ + ⟨v′⟩ by Corollary 8.

Altogether, it follows that, after degree d is finished, the elements of V_{min} are a minimal system of generators of ⟨M_{≤d}⟩, as we wanted to show. ⊓ ⊔

Remark 14 Let us collect some observations about this algorithm.

a) If we are only interested in a minimal system of generators of M (and not in a Gröbner basis), we can stop the algorithm after we have completed degree d_{max} = max{deg(v_{i}) | 1 ≤ i ≤ s}. In this case it suffices to append only the pairs {(i, s′) | 1 ≤ i < s′, γ_{i} = γ_{s′}, deg_{W} (σ_{is′}) ≤_{Lex} d_{max}} to the set B in steps 5) and 8’).

b) In addition, we could alter step 8’) and append the vector v′ instead of v to the list V_{min}. Then V_{min} would still contain a minimal homogeneous set of generators of M when the computation ends. These generators would not be contained in the initial tuple V anymore, but they would have the additional property that each vector is fully reduced against the previous ones.

The final part of the section is devoted to a result which will be essential for our discussion of the minimalization of the critical pairs. Namely, we are going to apply the algorithm of Corollary 13 to a reduced Gröbner basis and improve it significantly in that case. The main differences between both algorithms occur in step 7), where it suffices to compare terms instead of computing normal remainders, and in step 8), where we append v to both G and V_{min}.

Theorem 15 (Minimal Generators in a Reduced Gröbner Basis) In the situation of Theorem 11, let V = (v_{1}, …, v_{s}) be the reduced σ-Gröbner basis of M. Consider the following instructions.

1) Let B = ∅, W = V, G = ∅, s′ = 0, and V_{min} = ∅.

2) Let d be the smallest degree with respect to Lex of an element of B or of W. Form B_{d} and W_{d}, and delete their entries from B and W, respectively.

3) If B_{d} = ∅, continue with step 6). Otherwise, choose a pair (i, j) ∈ B_{d} and remove it from B_{d}.

4) Compute S′_{ij} = NR_{σ,G}(S_{ij}). If S′_{ij} = 0, continue with step 3).

5) Increase s′ by one, append g_{s′} = S′_{ij} to the tuple G, append the following set {(i, s′) | 1 ≤ i < s′, γ_{i} = γ_{s′}} to B, and continue with step 3).

6) If W_{d} = ∅, continue with step 9). Otherwise, choose v ∈ W_{d} and remove it from W_{d}.

7) If LT_{σ}(v) = LT_{σ}(g) for some g ∈ G, then replace the element g in G by v. Continue with step 6).

8) Increase s′ by one, append g_{s′} = v to the tuples G and V_{min}, and append {(i, s′) | 1 ≤ i < s′, γ_{i} = γ_{s′}} to the set B. Continue with step 6).

9) If B = ∅ and W = ∅, return V_{min} and stop. Otherwise, continue with step 2).

This is an algorithm which computes a subtuple V_{min} of V such that V_{min} is a minimal system of generators of M.

Proof. It suffices to show that this procedure has the same effect as running the algorithm of Corollary 13 on V.

First we use induction on d to show that, after we have finished some degree d, the tuple G has the same elements as V_{≤d}. Every element of V_{d} is appended to G at some point in step 7) or 8). On the other hand, if an element g_{s′} is put into G in step 5), it has a leading term which is not a multiple of an element of V_{<d}. Hence it is swapped out of G at some point in step 7).

Next we note that, after we have finished cycling through steps 3), 4), and 5) in degree d, the tuple G is a d-truncated minimal σ-Gröbner basis of M_{<d}.

Now we turn our attention to the loop described in steps 6), 7) and 8). Notice that the effect of steps 7) and 8) is independent of the order in which we choose the elements v ∈ W_{d} in step 6). Hence we can assume for the purposes of this proof that we always choose the vector v in W_{d} which has the minimal leading term with respect to σ. With this assumption, we show inductively that when we run steps 7) and 8) for some element v ∈ W_{d}, at each point the elements in G are a minimal σ-Gröbner basis of the module they generate, and the elements of V_{min} are a minimal system of generators of that module.

For the induction step, we have to consider two cases: either v is swapped into G in step 7) or appended to both G and V_{min} in step 8). In the first case, it suffices to show that the module generated by the elements of G does not change when we perform the swap, i.e. that the difference v − g is contained in this module. This follows from the observations that LT_{σ}(v − g) <_{σ} LT_{σ}(v) and all elements ṽ in V such that LT_{σ}(ṽ) <_{σ} LT_{σ}(v) are already in G. Since v−g ⟶^{V} 0, we have v−g ⟶^{G} 0. In the second case, it is clear that G continues to be a minimal Gröbner basis of the module it generates by Corollary 8, and V_{min} continues to be a minimal system of generators of that module by Corollary 10.

Finally, we note that in step 8) we can append v to G without passing to the normal remainder, since v is an element of a reduced Gröbner basis and thus irreducible. ⊓ ⊔

Remark 16 Let us make some observations about the preceding algorithm.

a) The proof of the proposition shows that the algorithm reconstructs the given reduced Gröbner basis inside G, and that G_{≤d} has the same elements as V_{≤d} after some degree d is finished.

b) Moreover, we note that in step 4) it is not necessary to compute the normal remainder NR_{σ,G}(S_{ij}). Rather, it suffices to perform a full leading term reduction.

c) The different elements NR_{σ,G}(S_{ij}) computed in step 4) and the elements v ∈ V_{d} which are swapped into G by step 7) are in 1 − 1 correspondence, since every new element computed in step 4) must have a new leading term in the leading term module of M. This new leading term must be the leading term of an element in the reduced Gröbner basis, hence it is swapped.

4 Minimalizing the Critical Syzygies

In this section we continue to use the assumptions and notation of the previous section. If we look at Theorem 11 and its proof, we can see that instead of treating all pairs (i, j) such that σ_{ij} is contained in the set of critical syzygies Σ, it would be enough to treat those pairs corresponding to a subset Θ ⊆ Σ which is a minimal system of generators of Syz_{P} (c_{1}t_{1}e_{γ_{1}}, …, c_{s}t_{s}e_{γ_{s}}).

In order to find Θ, we observe that the application of two of the rules for killing critical pairs given in (Gebauer and Möller, 1987) produces a minimal Gröbner basis of the module Syz_{P} (c_{1}t_{1}e_{γ_{1}}, …, c_{s}t_{s}e_{γ_{s}}) contained in the set Σ. From this we derive the idea to find Θ by applying Theorem 15. We need the following definition.

Definition 17 On the set of terms 𝕋^{n}⟨ε_{1}, …, ε_{s}⟩ in ⊕_{i=1}^{s} P (−d_{i}) we define a relation τ by letting

t ε_{i} ≥_{τ} t′ ε_{j} ⇔ \{ \begin{matrix}t t_{i} e_{γ_{i}} >_{σ} t′ t_{j} e_{γ_{j}}, or \\ t t_{i} e_{γ_{i}} = t′ t_{j} e_{γ_{j}} and i ≥ j \end{matrix}

for t, t′ ∈ 𝕋^{n} and i, j ∈ {1, …, s}. As in (Kreuzer and Robbiano, 2000), Lemma 3.1.2, it follows that τ is a module term ordering. It is called the term ordering induced by the tuple (t_{1}e_{γ_{1}}, …, t_{s}e_{γ_{s}}) and by σ.

By (Kreuzer and Robbiano, 2000), Proposition 3.1.3, the set Σ is a τ -Gröbner basis of the module Syz_{P} (c_{1}t_{1}e_{γ_{1}}, …, c_{s}t_{s}e_{γ_{s}}). Moreover, σ_{ij} is a homogeneous element of ⊕_{i=1}^{s} P (−d_{i}) of degree deg_{W} (σ_{ij}) = deg(lcm(t_{i}, t_{j})) + δ_{γ_{i}}. For all i, j ∈ \{1, …, s\}, we let t_{ij} = \frac{lcm(t_{i},t_{j})}{t_{i}}. Now the main result of Gebauer and Möller (1987) reads as follows.

Proposition 18 Consider the following instructions.

Rule 1. Delete in Σ all elements σ_{jk} such that there exists an index i in the

set {1, …, j − 1} such that t_{ki} divides t_{kj}. Call the resulting set Σ′. Rule 2. Delete in Σ′ all elements σ_{ik} such that there exists an index j in the

set {i + 1, …, k − 1} such that t_{kj} properly divides t_{ki}. Call the resulting

set Σ′′.

Rule 3. Delete in Σ′′ all elements σ_{ij} such that there exists an index k in the set ∈ {j +1, …, s} such that t_{ik} properly divides t_{ij} and t_{jk} properly divides t_{ji}. Call the resulting set Σ′′′.

Then the set Σ′′′ still generates Syz_{P} (c_{1}t_{1}e_{γ_{1}}, …, c_{s}t_{s}e_{γ_{s}}).

Remark 19 Let us interpret the previous proposition in another way. For 1 ≤ i < j ≤ s such that γ_{i} = γ_{j}, we have LT_{τ}(σ_{ij}) = t_{ji}ε_{j}. Hence Rules 1 and 2 can be restated as follows.

Rule 1’. Delete in Σ all elements σ_{ij} such that there exists an element σ_{i′j}

such that LT_{τ}(σ_{ij}) is a proper multiple of LT_{τ}(σ_{i′j}). Rule 2’. If, among the remaining elements, there are elements σ_{ij}, σ_{i′j} such

that LT_{τ}(σ_{ij}) = LT_{τ}(σ_{i′j}), then delete the one having the larger index max{i, i′}.

From Rules 1’ and 2’ it follows that the set Σ′′ is a minimal τ -Gröbner basis of the module Syz_{P} (c_{1}t_{1}e_{γ_{1}}, …, c_{s}t_{s}e_{γ_{s}}), i.e. the leading terms of the elements of Σ′′ minimally generate the leading term module.

In general, it is not true that Σ′′ is a minimal system of generators of the module Syz_{P} (c_{1}t_{1}e_{γ_{1}}, …, c_{s}t_{s}e_{γ_{s}}), as our next example shows. (For another example, see (Gebauer and Möller, 1987), 3.6.)

Example 20 Let P = ℚ[x, y, z] be standard graded, let r = 1, s = 4 and t_{1} = x^{3}z^{2}, t_{2} = x^{3}y^{4}, t_{3} = y^{5}z^{2}, t_{4} = x^{2}y^{5}z. Then we get σ_{12} = y^{4}ε_{1} − z^{2}ε_{2}, σ_{13} = y^{5}ε_{1}−x^{3}ε_{3}, σ_{14} = y^{5}ε_{1}−xzε_{4}, σ_{23} = yz^{2}ε_{2}−x^{3}ε_{3}, σ_{24} = yzε_{2}−xε_{4}, and σ_{34} = x^{2}ε_{3} − zε_{4}. By applying Rules 1 and 2, we get the minimal τ -Gröbner basis Σ′′ = {σ_{12}, σ_{24}, σ_{34}, σ_{13}} of Syz_{P} (t_{1}, t_{2}, t_{3}, t_{4}), since LT_{τ}(σ_{23}) = LT_{τ}(σ_{13}) and LT_{τ}(σ_{14}) = z · LT_{τ}(σ_{24}). Now we use Rule 3 and find Σ′′′ = Σ′′, but Σ′′′ is not a minimal system of generators of Syz_{P} (t_{1}, t_{2}, t_{3}, t_{4}), since we have σ_{13} = yσ_{12} + zσ_{24} − xσ_{34}.

Before continuing, let us introduce a new notion. If we have an element σ_{ij}

and perform a reduction step σ_{ij} ⟶^{ctσ_{i′j}} c′t′ε_{i} + c′′t′′ε_{i′}, where c, c′, c′′ ∈ K and

t, t′, t′′ ∈ 𝕋^{n}, we call this a head reduction step. (Notice that the j -indices have to match!) Similarly, we can define a tail reduction step as follows: σ_{ij} ⟶^{ctσ_{i′i}} c′t′ε_{i′} +c′′t′′ε_{j}. It is clear that a tail reduction step does not change the leading term of the element.

Proposition 21 The set Σ̃ = {−c_{j} · σ_{ij} | σ_{ij} ∈ Σ′′} is the reduced τ -Gröbner basis of the module Syz_{P} (c_{1}t_{1}e_{γ_{1}}, …, c_{s}t_{s}e_{γ_{s}}).

Proof. Since passing from Σ′′ to Σ̃ is equivalent to normalizing the leading coefficients, and since Σ′′ is a minimal τ -Gröbner basis, it remains to show that no tail reductions are possible among the elements of Σ̃. But if we perform a tail reduction on some element of Σ̃, we get an element of the form c̃t̃σ_{i′j} such that i′ < i. Here we have to have t̃= 1, since σ_{ij} is part of a minimal Gröbner basis. Now we obtain a contradiction to the minimality of i in Rule 2’. ⊓ ⊔ Remark 22 Let us apply the algorithm of Theorem 15 to the set Σ̃. We make the following observations.

a) A pair of pairs, i.e. a critical pair between two elements σ_{ij}, σ_{i′j′} yields an S-vector S_{((i,j),(i′,j′))} = c t σ_{ij} − c′ t′ σ_{i′j′} such that c, c′ ∈ K and t, t′ ∈ 𝕋^{n} and j = j′, since the two leading terms have to cancel. Without loss of generality, let i < i′. Then the result is c̃t̃σ_{ii′} for some c̃ ∈ K and t̃∈ 𝕋^{n}. The degree of such a pair of pairs is

deg_{W} (S_{((i,j),(i′,j))}) = deg_{W} (t̃) + deg_{W} (σ_{ii′})
= deg_{W} (\frac{lcm(t_{i},t_{i′},t_{j})}{t_{j}}) + deg_{W} (ε_{j})
= deg_{W} (lcm(t_{i}, t_{i′}, t_{j})) + δ_{γ_{j}}

b) During the course of the algorithm, a new Gröbner basis element can only be obtained from a pair of pairs if t̃ = 1. This is equivalent to gcd(t_{ij}, t_{i′j}) = 1.

Now we are ready to optimize the minimalization of the critical syzygies. To ease the notation, we shall minimalize the set Σ′′ instead of Σ̃. The lack of the normalization of the leading coefficients is clearly of no consequence. We need the following lemma.

Lemma 23 Let 1 ≤ i < j < m ≤ s and i′ ∈ {1, …, j − 1} \ {i}. Suppose there are terms t, t′, t′′ ∈ 𝕋^{n} \ {1} such that σ_{ij} = σ_{ii′} + t σ_{i′j} = t′ σ_{im} − t′′ σ_{jm} and σ_{i′m} = t σ_{i′j} + t′′ σ_{jm}. Then t, t′, and t′′ are pairwise coprime.

More precisely, given κ ∈ {1, …, n}, we define α = deg_{x_{κ}}(t_{i}), α′ = deg_{x_{κ}}(t_{i′}), β = deg_{x_{κ}}(t_{j}), and γ = deg_{x_{κ}}(t_{m}). Then one of the following four cases occurs.

1) We have α = γ > β and α > α′.

2) We have α′ = β > γ and α′ > α.

3) We have α = α′ > β and α > γ.

4) We have α = α′ = β > γ or α = β = γ > α′ or α′ = β = γ > α.

Proof. Comparing coefficients in the given equations yields the following equalities lcm(t_{i}, t_{j}) = lcm(t_{i}, t_{i′}) = lcm(t_{i′}, t_{m}) = t lcm(t_{i′}, t_{j}) = t′ lcm(t_{i}, t_{m}) = t′′ lcm(t_{j}, t_{m}). Thus the exponent of x_{κ} in these terms satisfies max{α, β} = max{α, α′} = max{α′, γ} = deg_{x_{κ}}(t) + max{α′, β} = deg_{x_{κ}}(t′) + max{α, γ} = deg_{x_{κ}}(t′′) + max{β, γ}. We distinguish the following four cases.

Case 1: Suppose that x_{κ} divides t. In this case, max{α, α′} > max{α′, β} yields α > α′ and α > β. Then α = max{α, α′} = max{α′, γ} shows α = γ, i.e. we have the inequalities stated in case 1) of the claim. Furthermore, it follows that γ = max{α, γ} = max{β, γ}, i.e. that x_{κ} divides neither t′ nor t′′.

Case 2: Suppose that x_{κ} divides t′. In this case, max{α, α′} > max{α, γ} yields α′ > α and α′ > γ. Then max{α, β} = max{α, α′} shows α′ = β, i.e. we have the inequalities stated in case 2) of the claim. Furthermore, it follows that β = max{α′, β} = max{β, γ}, i.e. that x_{κ} divides neither t nor t′′.

Case 3: If x_{κ} divides t′′, we argue analogously and obtain the inequalities stated in 3) as well as the fact that x_{κ} divides neither t nor t′.

Case 4: If x_{κ} divides neither t nor t′ nor t′′, an easy case-by-case argument yields the possibilities listed in 4). ⊓ ⊔

Proposition 24 (Minimalization of the Critical Syzygies) Let Σ′′ be the τ -Gröbner basis of Syz_{P} (c_{1}t_{1}e_{γ_{1}}, …, c_{s}t_{s}e_{γ_{s}}) defined in Proposition 18. Consider the following instructions.

1) Let B^{∗} = ∅, W = Σ′′, A = ∅, and Θ = ∅.

2) For all σ_{ij}, σ_{i′j} ∈ Σ′′ such that 1 ≤ i < i′ < j ≤ s, form the S-vector S_{((i,j),(i′,j))} = t̃σ_{ii′}, where t̃∈ 𝕋^{n}. If t̃= 1, append σ_{ii′} to B^{∗}.

3) Let d be the smallest degree with respect to Lex of an element of B^{∗} or W. Form B_{d}^{∗} and W_{d}, and delete their entries from B^{∗} and W, respectively.

4) If B_{d}^{∗} = ∅, continue with step 11). Otherwise, choose an element σ_{ij} ∈ B_{d}^{∗} and remove it from B_{d}^{∗}.

5) If LT_{τ}(σ_{ij}) ∈ LT_{τ}(A_{d}), then continue with step 4).

6) If LT_{τ}(σ_{ij}) = LT_{τ}(σ_{i′j}) for some element σ_{i′j} ∈ W_{d}, then remove σ_{i′j} from W_{d}, append it to A, and continue with step 4).

7) Find σ_{i′j} ∈ A_{<d} such that t_{ji} is a multiple of t_{ji′}. Then perform the head reduction step σ_{ij} ⟶^{σ_{i′j}} t̃σ_{kℓ}, where t̃ ∈ 𝕋^{n}, where k = min{i, i′}, and where ℓ = max{i, i′}. If t̃≠ 1, continue with step 4).

8) If LT_{τ}(σ_{kℓ}) ∈ LT_{τ}(A_{d}), then continue with step 4).

9) If LT_{τ}(σ_{kℓ}) = LT_{τ}(σ_{k′ℓ}) for some element σ_{k′ℓ} ∈ W_{d}, then remove the element σ_{k′ℓ} from W_{d}, append it to A, and continue with step 4).

10) If σ_{kℓ} ∈ B_{d}^{∗}, then delete σ_{kℓ} in B_{d}^{∗} and continue with step 7), applied to this element. Otherwise continue with step 4).

11) Append W_{d} to A and to Θ.

12) If B^{∗} = ∅ and W = ∅, return Θ and stop. Otherwise, continue with step 3).

This is an algorithm which computes a subset Θ ⊆ Σ′′ such that Θ is a minimal system of generators of Syz_{P} (c_{1}t_{1}e_{γ_{1}}, …, c_{s}t_{s}e_{γ_{s}}).

Proof. It suffices to show that the given instructions define an optimization of the application of Theorem 15 to the set Σ′′. The tuple A corresponds to G there, Θ corresponds to V_{min}, and B^{∗} corresponds to B.

The first significant difference occurs in step 2). Instead of producing the pairs of pairs inductively each time we find a new Gröbner basis element, we precompute them all at once. This is possible, since we know from Theorem 15 that we are merely recomputing the Gröbner basis Σ′′. Moreover, we do not store the pairs of pairs, but the S -vectors they generate, and we do not store S -vectors which are clearly useless by part b) of the remark following Proposition 21.

The main difference occurs in steps 5) through 10). Instead of computing the normal remainder of the S-vector, we perform leading term reductions only and check the result after each reduction step. When we choose an element σ_{ij} in step 4), it is not contained in A_{d}, since if an element σ_{kℓ} is appended to A in step 11) and cannot be contained in B_{d}^{∗} by step 10). But the element σ_{ij} could have a leading term in LT_{σ}(A_{d}) without being contained in A_{d}. We claim that, in this case, we know σ_{ij} ⟶^{A} 0, i.e. that σ_{ij} produces no new Gröbner basis element.

To prove this claim, we first note that clearly A is a subtuple of W at all times. Since the elements of W are fully interreduced, the tail of σ_{ij} cannot be a leading term of an element of A_{d}. On the other hand, if LT_{τ}(σ_{ij}) = LT_{τ}(σ_{i′j}) for σ_{i′j} ∈ A_{d}, then the leading term of the result of the reduction of σ_{ij} by σ_{i′j} is the tail of σ_{ij}. Hence σ_{ij} can be tail reduced using A_{<d}. By applying the same argument to the result of this tail reduction step, we conclude that after several tail reductions using A_{<d}, we reach an element of A_{d}, and the claim follows.

The next possibility for σ_{ij} is that it is head irreducible with respect to A. In this case its leading term is equal to LT_{τ}(σ_{i′j}) for some σ_{i′j} ∈ W_{d}. Now Theorem 15 says that we should put NR_{τ,A}(σ_{ij}) into A and later swap it for σ_{i′j}. But, as we just saw, we can tail reduce σ_{ij} using A_{<d} until we reach σ_{i′j}. Thus the normal remainder is σ_{i′j} and is put into A immediately, i.e. without actually performing the tail reductions and without a later swap.

The last possibility for LT_{τ}(σ_{ij}) is that it can be reduced using A_{<d}. This reduction step is performed in step 7). Let us discuss the possible outcomes.

If the result is of the form t̃σ_{kℓ} with t̃ ∈ 𝕋^{n} \ {1}, then σ_{kℓ} has a lower degree and satisfies σ_{kℓ} ⟶^{A} 0, because A contains a truncated Gröbner basis. Consequently, we have σ_{ij} ⟶^{A} 0 and step 4) of 15 tells us to try the next S-vector.

If the result of the head reduction step has one of the new leading terms provided by the elements of W_{d}, we notice this in step 8) or 9). In the first case, the element of V_{d} has already been swapped into A and nothing needs to be done. In the second case, we perform the swap in step 9).

If the result is an element σ_{kℓ} of degree d which can be further head reduced, we check in step 10) whether σ_{kℓ} ∈ B_{d}^{∗}. In that case σ_{ij} and σ_{kℓ} have the same reductions and it suffices to treat σ_{kℓ} in step 7). Otherwise, we claim that σ_{kℓ} is one of the elements of B_{d}^{∗} which has been dealt with already, i.e. that we can go back to step 4) and treat the next element of B_{d}^{∗}.

To prove this claim, we first use σ_{ij} ∈ B_{d}^{∗} in order to write σ_{ij} = t′ σ_{im} +t′′ σ_{jm} with t′, t′′ ∈ 𝕋^{n} \ {1} and j < m ≤ s. Secondly, by step 7), we have the equality σ_{ij} = t σ_{i′j} ± σ_{kℓ}, where σ_{kℓ} = ±σ_{i′i} and t ∈ 𝕋^{n} \ {1}. By looking at the coefficient of e_{j} in the equation σ_{ii′} = t′ σ_{im} − t σ_{i′j} − t′′ σ_{jm}, we see that t lcm(t_{i′}, t_{j}) = t′′ lcm(t_{j}, t_{m}). This term is a multiple of t_{i′} and of t_{m}. Hence it is of the form t̃ lcm(t_{i′}, t_{m}) for some t̃∈ 𝕋^{n}, and we have σ_{ii′} = t′ σ_{im} − t̃σ_{i′m}. If t̃ ≠ 1, then σ_{kℓ} is a pair of pairs, i.e. it is either in B_{d}^{∗} or it is one of the elements of B_{d}^{∗} treated before. Hence the claim follows if we can show that t̃= 1 does not happen.

Suppose that t̃ = 1. Then we are in the situation of the lemma. Since the conditions of steps 8) and 9) did not apply, it follows that σ_{kℓ} can be further head reduced using A_{<d}. Hence there exist u, u′ ∈ 𝕋^{n} and j′ < max{i, i′} such that σ_{i′i} = u σ_{i′j′} + u′ σ_{j′i} and u ≠ 1 or u′ ≠ 1, depending on whether i > i′ or i < i′.

Now we show that u′ ≠ 1 is impossible. We use the notation of the lemma and let δ = deg_{x_{κ}}(t_{j′}), where x_{κ} is one of the indeterminates occurring in t, i.e. where case 1) of the lemma holds. Then the equation lcm(t_{i′}, t_{i}) = u lcm(t_{i′}, t_{j′}) = u′ lcm(t_{i}, t_{j′}) shows max{α, α′} > max{α, δ}. This implies α′ > α and α′ > δ, in contradiction to case 1) of the lemma. Similarly, we can show that u ≠ 1 is impossible. This concludes the proof of the claim.

Altogether, it follows that steps 5) – 10) implement the full reduction of σ_{ij} together with the swapping procedure of step 7) of 15. Hence the remaining elements of W_{d} are precisely the minimal generators of degree d we are looking for, and they have to be appended to Θ in step 11). ⊓ ⊔

Let us apply this algorithm in the situation of Example 20.

Example 25 Our task is to minimalize W = Σ′′ = {σ_{12}, σ_{13}, σ_{24}, σ_{34}}, where we have deg_{W} (σ_{12}) = 9, deg_{W} (σ_{13}) = 10, and deg_{W} (σ_{24}) = deg_{W} (σ_{34}) = 9.

In step 2), the algorithm constructs the set B^{∗}. The pair of pairs ((2, 4), (3, 4)) yields S_{((2,4),(3,4))} = zσ_{24} − xσ_{34} = −yz^{2}ε_{2} + x^{3}ε_{3} = σ_{23}, and this is the only element of B^{∗}. Notice that it has degree 10.

In step 3), the algorithm starts to operate in degree d = 9. Since B_{9}^{∗} = ∅, it appends σ_{12}, σ_{24}, and σ_{34} to A and Θ in step 11).

Next we process degree 10. In step 4), we choose σ_{23} ∈ B_{10}^{∗} and set B_{10}^{∗} = ∅. Then, in step 6), we find LT_{τ}(σ_{23}) = x^{3}ε_{3} = LT_{τ}(σ_{13}), where σ_{13} ∈ W_{10}. Hence σ_{13} is removed from W_{10} and appended to A in step 6).

Thus we have B^{∗} = ∅ and W = ∅ at this point, and step 12) returns the set Θ = {σ_{12}, σ_{24}, σ_{34}}. We note that this is the correct answer, and there is an improvement over the application of Proposition 18 coming from the fact that in step 6) we merely check LT_{τ}(σ_{ij}) ∈ LT_{τ}(W_{d}) rather than σ_{ij} ∈ W_{d}.

The following example provides a case where it is actually necessary to do one head reduction step in 7) in order to find a previously undiscovered nonminimal critical syzygy.

Example 26 Let P = ℚ[x_{1}, …, x_{5}] be standard graded, let r = 1 and s = 4. The terms t_{1} = x_{2}^{2}x_{3}^{6}x_{4}x_{5}^{2}, t_{2} = x_{1}^{8}x_{2}x_{4}x_{5}^{4}, t_{3} = x_{1}^{8}x_{2}^{2}x_{3}^{6}, and t_{4} = x_{1}^{8}x_{3}^{6}x_{5}^{4} yield the critical syzygies σ_{12} = x_{1}^{8}x_{5}^{2}ε_{1}−x_{2}x_{3}^{6}ε_{2}, σ_{13} = x_{1}^{8}ε_{1}−x_{4}x_{5}^{2}ε_{3}, σ_{14} = x_{1}^{8}x_{5}^{2}ε_{1}− x_{2}^{2}x_{4}ε_{4}, σ_{23} = x_{2}x_{3}^{6}ε_{2} − x_{4}x_{5}^{4}ε_{3}, σ_{24} = x_{3}^{6}ε_{2} − x_{2}x_{4}ε_{4}, and σ_{34} = x_{5}^{4}ε_{3} − x_{2}^{2}ε_{4}. Here steps 1) and 2) of Proposition 18 discard σ_{23} and σ_{14}, because we have LT_{τ}(σ_{23}) = x_{4}x_{5}^{4}ε_{3} = x_{5}^{2} LT_{τ}(σ_{13}) and LT_{τ}(σ_{14}) = x_{2}^{2}x_{4}ε_{4} = x_{2} LT_{τ}(σ_{24}). Thus we have Σ′′ = {σ_{12}, σ_{13}, σ_{24}, σ_{34}}. We note that we have deg_{W} (σ_{12}) = 21, deg_{W} (σ_{13}) = 19, and deg_{W} (σ_{24}) = deg_{W} (σ_{34}) = 20. But Σ′′ is not minimal, since we have σ_{12} = x_{5}^{2}σ_{13} − x_{2}σ_{24} + x_{4}σ_{34}.

Now we apply our algorithm. In step 2), we have to compute S_{((2,4),(3,4))} = x_{2}σ_{24} − x_{4}σ_{34} = x_{2}x_{3}^{6}ε_{2} − x_{4}x_{5}^{4}ε_{3} = σ_{23}. Thus σ_{23} is appended to B^{∗}. It has degree deg_{W} (σ_{23}) = 21. No further pairs of pairs are found.

In step 3), the algorithm starts to operate in degree d = 19. We have B_{19}^{∗} = ∅ and W_{19} = (σ_{13}). Thus we append σ_{13} to A and Θ in step 11). Next we pass to degree d = 20. We still have B_{20}^{∗} = ∅, but now we get W_{20} = (σ_{24}, σ_{34}). In step 11), σ_{24} and σ_{34} are put into A and Θ.

When we start processing degree d = 21, we have to choose σ_{23} ∈ B_{21}^{∗} and set B_{21}^{∗} = ∅ in step 4). The leading term LT_{τ}(σ_{23}) = x_{4}x_{5}^{4}ε_{3} is not equal to one of the leading terms of the elements of A_{21} or W_{21}. But we can perform a head reduction step in 7), namely σ_{23} ⟶^{σ_{13}} −σ_{12}. Here step 8) does not apply, but in step 9) we have LT_{τ}(σ_{12}) ∈ LT_{τ}(W_{21}). Thus we continue by removing σ_{12} from W_{21} and appending it to A.

Finally, we get B^{∗} = ∅ and W = ∅. The algorithm returns Θ = {σ_{13}, σ_{24}, σ_{34}}. As mentioned above, the non-minimal critical syzygy σ_{12} was discovered after one head reduction step in 7).

5 An Optimized Buchberger Algorithm

In this section we combine the results obtained so far. We continue to use the notation and conventions of the previous sections. In particular, we let P = K[x_{1}, …, x_{n}] be a polynomial ring over a field K which is positively graded by a matrix W ∈ Mat_{m,n}(ℤ), and we let M be a graded submodule of a graded free P -module F = ⊕_{i=1}^{r} P (−δ_{i}) which is generated by a tuple V = (v_{1}, …, v_{s}) of homogeneous vectors. Furthermore, we let σ be a module term ordering on 𝕋^{n}⟨e_{1}, …, e_{r}⟩.

In the following theorem the sets of critical pairs corresponding to the sets of critical syzygies considered earlier are denoted by the normal letters corresponding to their calligraphic versions.

Theorem 27 (Optimized Buchberger Algorithm) In the above situation, consider the following sequence of instructions.

1) Let W = V, A = ∅, B = ∅, B^{∗} = ∅, G = ∅, and let s′ = 0.

2) Let d be the smallest degree w.r.t. Lex of an element of B or W. Form B_{d}, B_{d}^{∗}, W_{d}, and delete their entries from B, B^{∗}, and W, respectively.

3) Apply MinPairs(A, B_{d}, B_{d}^{∗}).

4) If B_{d} = ∅, then continue with step 7). Otherwise, choose a pair (i, j) in B_{d}, delete it from B_{d}, and append it to A.

5) Compute S_{ij} and S′_{ij} = NR_{σ,G}(S_{ij}). If S′_{ij} = 0, then continue with 4).

6) Increase s′ by one, append g_{s′} = S′_{ij} to G, perform Update(B, B^{∗}, g_{s′}), and continue with step 4).

7) If W_{d} = ∅ then continue with 10). Otherwise, choose v ∈ W_{d} and delete it in W_{d}.

8) Compute v′ = NR_{σ,G}(v). If v′ = 0, continue with step 7).

9) Increase s′ by one, append g_{s′} = v′ to G and perform Update(B, B^{∗}, g_{s′}). Then continue with step 7).

10) If B = ∅ and W = ∅, then return G and stop. Otherwise, continue with step 2).

Here the procedure Update(B, B^{∗}, g_{s′}) is defined as follows.

U1) Form the set C = {(i, s′) | 1 ≤ i < s′, γ_{i} = γ_{s′}}. U2) Delete from C all pairs (j, s′) for which there exists an index i in the set

{1, …, j − 1} such that t_{s′i} divides t_{s′j}. U3) Delete from C all pairs (i, s′) for which there exists an index j in the

set {i + 1, …, s′ − 1} such that t_{s′j} properly divides t_{s′i}. U4) Find in C all pairs (i, s′) and (j, s′) such that 1 ≤ i < j < s′ and

such that gcd(t_{is′}, t_{js′}) = 1. For each of these, check if (i, j) is already contained in B^{∗} and append it if necessary.

U5) Append the elements of C to B and stop.

Furthermore, the procedure MinPairs(A, B_{d}, B_{d}^{∗}) is defined as follows.

M1) If B_{d}^{∗} = ∅, then stop. Otherwise, choose a pair (i, j) in B_{d}^{∗} and remove

it from B_{d}^{∗}. M2) If t_{ji} = t_{ji′} for some pair (i′, j) ∈ A, then continue with step M1). M3) If t_{ji} = t_{ji′} for some pair (i′, j) ∈ B_{d}, then remove this pair from B_{d} and

append it to A. Continue with step M1). M4) Find (i′, j) ∈ A such that t_{ji′} divides t_{ji}. Let k = min{i, i′}, and let

ℓ = max{i, i′}. If gcd(t_{ij}, t_{i′j}) ≠ 1, then continue with M1). M5) If t_{ℓk} = t_{ℓk′} for some pair (k′, ℓ) ∈ A, then continue with M1). M6) If t_{ℓk} = t_{ℓk′} for some pair (k′, ℓ) ∈ B_{d}, then delete this pair in B_{d}, append

it to A, and continue with M1). M7) If (k, ℓ) ∈ B_{d}^{∗}, then delete (k, ℓ) in B_{d}^{∗} and continue with M4), applied

to this pair. M8) Continue with step M1).

Altogether, we obtain an algorithm which computes a tuple G whose elements form a homogeneous σ-Gröbner basis of M. Moreover, the set of pairs which are treated at some time in steps 4) – 6) of the algorithm corresponds to a minimal system of generators of the module Syz_{P} (c_{1}t_{1}e_{γ_{1}}, …, c_{s′}t_{s′}e_{γ_{s′}}).

Proof. The main algorithm of this theorem agrees with the Homogeneous Buchberger Algorithm (see Theorem 11), except for the introduction of the procedure MinPairs(A, B_{d}, B_{d}^{∗}) in step 3) and the alteration of the enlargement of B in steps 5) and 8) of Theorem 11 which is now performed by the procedure Update(B, B^{∗}, g_{s′}).

The foundation for these changes is the material presented above, especially Proposition 24. In steps 4) – 6) we want to treat only those pairs (i, j) for which the corresponding elements σ_{ij} are contained in the minimal system of generators Θ of the graded P -module Syz_{P} (c_{1}t_{1}e_{γ_{1}}, …, c_{s′}t_{s′}e_{γ_{s′}}).

Procedure Update(B, B^{∗}, g_{s′}) applies Rules 1) and 2) of Gebauer-Möller in steps U2) and U3), respectively. Moreover, notice that step U4) computes all pairs of pairs which satisfy the condition of part b) of Remark 22, and stores the pairs corresponding to the resulting S-vectors in B^{∗}.

Thus, in order to minimalize the critical pairs we process, we need to apply Proposition 24 to the set of critical syzygies corresponding to the set of critical pairs B, where we can refrain from computing the pairs of pairs, because they have already been generated and stored in B^{∗}. This task is performed by the procedure MinPairs(A, B_{d}, B_{d}^{∗}). Its steps M1) – M8) are easy translations of steps 4) – 10) of Proposition 24 into the language of pairs. Notice that we have LT_{τ}(σ_{ij}) = LT_{τ}(σ_{kℓ}) if and only if j = ℓ and t_{ji} = t_{ℓk}. Altogether, Update(B, B^{∗}, g_{s′}) and MinPairs(A, B_{d}, B_{d}^{∗}) make sure that only the pairs corresponding to Θ are treated at some point in steps 3) – 6).

Finally, we remark that A is used to keep track of the pairs (i, j) for which σ_{ij} is in that part of the minimal τ -Gröbner basis Σ′′ of Syz_{P} (c_{1}t_{1}e_{γ_{1}}, …, c_{s′}t_{s′}e_{γ_{s′}}) which has been computed so far. Thus it is updated when a non-minimal element of Σ′′ is found in step M3) or step M6), and when a pair corresponding to an element of Θ is chosen for treatment in step 3). ⊓ ⊔

Let us illustrate the performance of this algorithm by a simple example. It shows that cases like Example 20 occur naturally during actual Gröbner basis computations.

Example 28 Let P = ℚ[x, y, z] be standard graded, let σ = DegLex, let r = 1, and let M ⊆ P be the homogeneous ideal generated by the polynomials v_{1} = x^{3}z^{2} + x^{2}y^{2}z, v_{2} = x^{3}y^{8}, and v_{3} = y^{10}z^{2}. Then the leading terms are t_{1} = x^{3}z^{2}, t_{2} = x^{3}y^{8}, and t_{3} = y^{10}z^{2}. Let us follow the steps of the Optimized Buchberger Algorithm.

The first degree is d = 5. Since B_{5} = ∅, the first actions are to choose v_{1} ∈ W_{5} in step 7) and append g_{1} = v_{1} to G in step 9). Then we continue with d = 11 and choose v_{2} ∈ W_{11} in step 7). Since v′ = NR_{σ,G}(v_{2}) = v_{2}, we appendg_{2} = v_{2} to G in step 9) and update the set of pairs. The result is B = {(1, 2)} and B^{∗} = ∅. Now we have to treat the degree d = 12. Notice that the degree of the pair (1, 2) is 13. Hence B_{12} = ∅ and we have to choose v_{3} ∈ W_{12} in step 7). Since v′ = NR_{σ,G}(v_{3}) = v_{3}, we appendg_{3} = v_{3} to G in step 9) and update the set of pairs. In step U1), we form C = {(1, 3), (2, 3)}. In step U2), we obtain t_{31} = x^{3} = t_{32}, and therefore (2, 3) is deleted in C. The result is B = {(1, 2), (1, 3)} and B^{∗} = ∅. This completes degree 12, and we continue with degree 13.

We choose the pair (1, 2) in step 4) and append it to A. Then we compute S_{12} = y^{8}g_{1} − z^{2}g_{2} = x^{2}y^{10}z and S′_{12} = NR_{σ,G}(S_{12}) = x^{2}y^{10}z. Thus we have a new Gröbner basis element g_{4} = x^{2}y^{10}z and need to update the pairs again. In step U1), we form C = {(1, 4), (2, 4), (3, 4)}. Step U2) does not apply, but in step U3) we remove the pair (1, 4) from C, since t_{42} = x properly divides t_{41} = xz. Now we check that t_{24} = y^{2}z properly divides t_{23} = y^{2}z^{2} and t_{34} = x^{2} properly divides t_{32} = x^{3}. Hence the pair (2, 3) is appended to B^{∗}.

At this point we have finished degree 13, and we have the following situation: A = {(1, 2)}, B = {(1, 3), (2, 4), (3, 4)}, B^{∗} = {(2, 3)}, G = {g_{1}, …, g_{4}}, and s′ = 4. The next degree is d = 14, where we have to deal with the pairs in B_{14} = {(2, 4), (3, 4)}. Since B_{14}^{∗} = ∅, we choose (2, 4) in step 4) and append it to A. Then we compute S_{24} = 0 and continue by choosing (3, 4) in B_{14} and adding it to A. Again S_{34} = 0, and degree 14 is finished.

Now we start degree 15 by performing MinPairs(A, B_{15}, B_{15}^{∗}), where we have A = {(1, 2), (2, 4), (3, 4)}, B_{15} = {(1, 3)} and B_{15}^{∗} = {(2, 3)}. In step M1), we choose (2, 3). In step M3), we discover t_{32} = x^{3} = t_{31}, where (3, 1) ∈ B_{15}. Hence (1, 3) is deleted in B_{15} and appended to A. Then the procedure is finished, and the facts that B_{15} = ∅ as well as W_{15} = ∅ allow us to return G and stop.

As in Example 20, we have found one useless pair, namely the pair (1, 3) in degree 15, which would not have been discovered by the Gebauer-Möller Installation, and which we were able to discard by a simple combinatorial check.

Remark 29 Let us discuss the efficiency of the algorithm of Theorem 27.

a) Steps U2) and U3) of this algorithm correspond to Rules 1) and 2) of the Gebauer-Möller installation. However, Rule 3 is not performed by the procedure Update(…), but by step M2) of the procedure MinPairs(…). In fact, step M2) gets rid of more pairs than Rule 3, because Rule 3 requires (i, j) ∈ B_{d}^{∗} ∩ B_{d}, whereas we only need a pair (i, j) ∈ B_{d}^{∗} such that LT_{τ}(σ_{ij}) = LT_{τ}(σ_{i′j}) for some (i′, j) ∈ B_{d}.

b) A potential drawback of our approach is that the number of pairs of pairs considered in step U4) is quadratic in the number of elements of C surviving steps U2) and U3). But that number is usually fairly small. Hence the cost of U4) and the cardinality of B^{∗} tend to be rather small. On the other hand, we do not need to check Rule 3 for all elements of the list B which is usually rather long. Our experiments suggest that, on average, the overhead of the two approaches is comparable.

c) Our procedure MinPairs(…) is very efficient in treating the elements of B_{d}^{∗}. Each time we loop through steps M2) – M8), we delete one pair in B_{d}^{∗}, and B_{d}^{∗} is never enlarged. In practice, we find that the lists B_{d}^{∗} are generally small. Hence our algorithm harnesses the full power and efficiency of the Gebauer-Möller installation, while it simultaneously kills all unnecessary pairs at a comparatively small cost.

6 Experimental Data and Conclusions

In this section we want to provide the reader with some experimental numerical data which illustrate the performance of the Optimized Buchberger Algorithm 27 as well as technical observations coming from an implementation in an experimental version of the “CoCoA 5” library in C++.

In the following table, we compare the application of Rules 1) – 3) of Proposition 18 to our procedures Update(…) and Minpairs(…) in Theorem 27, i.e. to the algorithm of Proposition 24. Let us point out that our procedure always minimalizes the critical pairs, independent of the order of the underlying terms. (Non-minimal critical pairs are recognized at different steps, though.) For the Gebauer-Möller installation, however, the number of undiscovered nonminimal critical pairs depends strongly on this order.

To aid the reader in understanding this table, let us explain the meaning of the symbols.

• #(G) is the cardinality of the reduced Gröbner basis of the corresponding ideal.

• #(Σ) is the total number of pairs, i.e. #(Σ) = \binom{#(G)}{2}.

• #(Σ′′) is the number of pairs surviving Rules 1) and 2), i.e. the cardinality of the reduced Gröbner basis of pairs.

• B is the number of pairs killed by Rule 3), the Gebauer-Möller “Backwards” criterion.

• M23 is the number of pairs killed by steps M2) and M3) in Theorem 27.

• M48 is the number of pairs killed by steps M4) – M8) in Theorem 27.

• Gain = M23+M48−B, i.e. the number of newly discovered non-minimal critical pairs.

• #(Θ) is the cardinality of a minimal system of generators of the syzygies of the leading terms. Hence we have #(Θ) = #(Σ′′) − M23 − M48

#(G)  #(Σ) #(Σ′′)  B M23 M48 Gain #(Θ)
Tˆ 51  83  3,403  250  7  7  0  0  243
Twomat3  109  5,886  741  15  26  1 12  714
Alex3  211  22,155  684  54  56  1  3  627
Gaukwa4  267  35,511 1,772 101 113  3 15 1,656
Kin1  306  46,665 3,411  70 172  0 102 3,239
Wang (Lex)  317  50,086 1,457  60  61  7  8 1,389
Cyclic 7  443  97,903 2,651  17  17  0  0  681
Hairer-2  506 127,765 5,305 150 152  4  6 5,149
Hom-Gonnet  854 364,231 11,763 587 648  27 88 11,088
Mora-9  4,131 8,530,515 46,395 1,930 1,914  23  7 44,458

The rows of this table correspond to standard examples of Gröbner basis computations. A file containing a description of every example can be downloaded at

 ftp://cocoa.dima.unige.it/papers/CaboaraKreuzerRobbiano03.cocoa

Moreover, a file containing the list of leading terms of the reduced Gröbner basis for each example can be downloaded at

ftp://cocoa.dima.unige.it/papers/CaboaraKreuzerRobbiano03 2.cocoa

Technical note: In the well-known example “Cyclic 7” we have homogenized using a new smallest indeterminate (see the file mentioned above).

For the reader who would like to run his own tests, we note that #(G), #(Σ), and #(Θ) are invariants of the reduced Gröbner basis. But the effect of both the Gebauer-Möller installation and our Optimized Buchberger Algorithm depend strongly on the order in which the elements of Σ are produced during a Gröbner basis computation. For instance, this means that it depends on the chosen selection strategy. In our implementation pairs are kept ordered in increasing DegLex ordering, reductors are kept in the same order they are produced, reductors of the same degree are kept interreduced, and the reduction strategy is full reduction.

The following table shows some timings. It compares Singular 2.0.0 with the current experimental version of CoCoA 5 using the GM and CKR pair handling algorithms. Timings are in seconds for Linux running on an Athlon 2000+ CPU with 1.5GB RAM. All computations are over the rationals where the timings of the base field operations in Singular and CoCoA seem to be comparable.

Technical note: The reason why we include a comparison with Singular is an explicit request made by a referee, who suggested comparing our timings with “another efficient implementation”. The table below indicates that both Singular and CoCoA 5 have efficient implementations of the Buchberger algorithm, and that our new algorithm has at least the same efficiency.

Singular 2.0.0 CoCoA5 GM CoCoA5 CKR
Tˆ 51 (Lex)  149.32  7.28  7.14
Twomat3  1.21  8.66  8.50
Alex3  <<1  0.54  0.56
Gaukwa4  80.30  99.31  98.57
Kin1  407.09  89.25  87.41
Wang (Lex)  >1200  382.86  379.31
Cyclic 7  >1200  76.61  76.65
Hairer-2  79.36  141.83  139.76
Hom-Gonnet  3.97  4.55  4.95
Mora-9  30.53  86.17  89.75

Conclusions

First of all, let us collect some technical observations based on our implementation of the Optimized Buchberger Algorithm.

a) When we apply Rules 1 and 2 of Proposition 18, the remaining set of pairs Σ′′ is usually almost a minimal system of generators of the module Syz_{P} (c_{1}t_{1}e_{γ_{1}}, …, c_{s′}t_{s′}e_{γ_{s′}}). Thus both Rule 3 and our algorithm kill comparatively few pairs. Nonetheless, over the rationals (or other costly fields), the saving is worthwhile because the treatment of each single pair can take a long time.

b) Steps M5) – M7) in the Optimized Buchberger Algorithm are independent. Hence it is possible to order them in such a way that the computational cost is minimized. This may be important if there is a large number of elements in B_{d}^{∗} to be processed, since the operations may have substantially different computational costs.

c) All operations in our procedures Update(...) and MinPairs(...) have been greatly eased by memorizing the terms t_{ij}, t_{ji} and lcm(t_{i}, t_{j}) directly in the pair data type.

d) When a search is performed on the pairs in A, B, or B_{d}, full advantage can be taken of the fact that we may rely on data structures which allow logarithmic search costs.

Looking at the timings above, we see that, on average and with comparable implementations, our new algorithm is faster than the Gebauer-Möller installation. In some examples, the gains are relatively small, and in exceptional cases, the structure of the combinatorial data produces a larger overhead for our algorithm than for the Gebauer-Möller installation.

Acknowledgments

The third author is grateful to the organizers of the First International Congress of Mathematical Software (Beijing 2002) for their hospitality and the possibility to present his work to a wide audience. An extended abstract of this paper was published in the proceedings of the congress (see (Caboara, Kreuzer and Robbiano, 2002)).

References

Buchberger, B. (1965). Ein Algorithmus zum Auffinden der Basiselemente des Restklassenrings nach einem nulldimensionalen Polynomideal. Ph.D. Thesis. Universität Innsbruck.

Buchberger, B. (1979). A criterion for detecting unnecessary reductions in the construction of Groebner bases. Proc. EUROSAM 79. Springer LNCS 72, 3–21.

Buchberger, B. (1985). Groebner Bases: An Algorithmic Method in Polynomial Ideal Theory. In: (N.K. Bose, Ed.) Multidimensional Systems Theory. D. Reidel Publ. Comp. Pp. 184–232.

Caboara, M., Kreuzer, M. and Robbiano, L. (2002) Minimal sets of critical pairs. In: (A. Cohen, X. Gao and N. Takayama, Eds.) Mathematical Software, Proc. Conf. Beijing 2002. World Scientific. Pp. 390–404

CoCoA (2001). A system for doing Computations in Commutative Algebra.

Available via anonymous ftp from cocoa.dima.unige.it Faugère, J.C. (2002). A new efficient algorithm for computing Gröbner bases

without reduction to zero (F5). In: (T. Mora, Ed.) Symbolic and Algebraic Computation, Proc. Conf. ISSAC 2002. ACM Press. Pp. 75–83

Gebauer, R. and Möller, H.M. (1987). On an installation of Buchberger’s

algorithm. J. Symbolic Computation, 6: 257–286. Kreuzer, M. and Robbiano, L. (2000). Computational Commutative Algebra 1.

Springer, Heidelberg. Kreuzer, M. and Robbiano, L. (In preparation). Computational Commutative

Algebra 2. Springer, Heidelberg.