2.2 The STZS-algorithm

Let $S = \{g_1, \ldots, g_q\}$ be a standard basis of $I \subseteq K[x]^r$.

For $K[x]^q = \sum^{q}_{i=1} K[x] e_i$ we choose the following monomial-weighted ordering <₁ (depending on S): $x^\alpha e_i <_1 x^\beta e_j$ if and only if either $L(x^\alpha g_i) < L(x^\beta g_j)$ or $L(x^\alpha g_i) = L(x^\beta g_j)$ and i > j.

For g_i, g_j, having the leading term in the same component, that is $L(g_i) = x^{\alpha_i} e_k, L(g_j) = x^{\alpha_j} e_k$ we consider spoly (g_i, g_j) := m_jig_i - m_ijg_j with $m_{ji} = c(g_j) {lcm(L(g_i),\, L(g_j))\over x^{\alpha_i}}$.

Because S is a standard basis we obtain ([SI], Corollary 1.11)

$$(1 + h_{ij}) (m_{ji} g_i - m_{ij} g_j) = \sum \xi^{ij}_\nu g_\nu$$

with L(h_ij) < 1 if $h_{ij} \not= 0$ and $L(\xi^{ij}_\nu g_\nu) < L(m_{ji}g_i)$.

For j > i such that g_i, g_j have leading term in the same component, let

$$\tau_{ij} := (1 + h_{ij}) (m_{ji} e_i - m_{ij} e_j) - \sum \xi^{ij}_\nu e_{\nu}.$$

Let ker $(K[x]^q \to K[x]^r, \sum w_i e_i \mapsto \sum w_i g_i)$ denote the module of syzygies, syz(I), of $\{g_1, \ldots, g_q\}$. The following proposition was proved independently by F. O. Schreyer, W. Trinks, G. Zacharias and D. A. Spear.

Proposition 2..1   With respect to the ordering <₁ the following holds:

1)

$L(\tau_{ij}) = m_{ji} e_i$.

2)

$\{\tau_{ij} \mid i < j$ s.t. L(g_i), L(g_j) are in the same component $\}$ is a standard basis for syz(I).

For a proof see, for example, [S] or [SI].

The main advantage of this algorithm is that the spolynomials always reduce to zero and thus, the sets of elements and of pairs do not change during the computation. It also allows us to consider only pairs built from one fixed element at the same time which results in much smaller pair sets. The knowledge of the leading terms of the syzygies is used to avoid useless computations which means cancelling those pairs the syzygy of which has a leading term divisible by another.

Considering the n-th iterated module of this resolution with the (n-1)-th iterated monomial-weighted ordering, the leading term of an arbitrary STZS-syzygy multiplied with the corresponding weight-monomial is just the lcm of an n-tupel of initial terms of the input. Therefore, an n-th syzygy of the STZS-resolution corresponds to a critical n-tupel in the terminology of [MM], Part II. The reduction of the associated spolynomial to zero corresponds to the computation of the lift of the morphism of leading terms to the complete generators described in Lemma 7.6 there. However, the step-by-step inspection of prospective leading terms gives the opportunity to compute always relatively to a minimal G-resolution of the leading terms. Hence, one of the problems of [MM] and [MM1] disappears here as the STZS-resolution is a minimal T-resolution.

The STZS-algorithm works not only for polynomial rings or their localizations, but also for factor rings. Assume $A=k[\underline{x}]/I$ be the factor of a polynomial ring after a certain ideal and let $I=(f_1,\ldots,f_m)$ be given by a standard (Groebner) basis. Define the normal form with respect to I of an element of an arbitrary module to be the component-wise normal form.

Definition 2..2   A subset G of a module $M\subset A^n$ is called a standard basis for M if

• the elements of G are given by representatives in normal form with respect to I and
• the leading term lt(m) of any element $m\in M$ in normal form with respect to I is divisible by some leading term lt(g) for $g\in G$.

Assume $g_i\in G$ and lt(g_i)=m*e_i. Denote by kgv_ij the lowest common multiple of m and lt(f_j). Then $(kgv_{ij}/m)*g_i-(kgv_{ij}/lt(f_j))*f_je_i\in M$ and, therefore, (G is standard basis!):

$$(1+h_{ij})((kgv_{ij}/m)*g_i-(kgv_{ij}/lt(f_j))*f_j)=\sum h_k*g_k \ \ \ mod\ I,$$

with $h_k\in k[\underline{x}]$ and lt(h_k*g_k)<kgv_ij*e_i. Now, set

$$\nu_{ij}=(1+h_{ij})(kgv_{ij}/m)*e_i-\sum h_k*e_k.$$

Proposition 2..3   With respect to the ordering <₁ the following holds:

1)

$lt(\nu{ij}) = (kgv_{ij}/m) e_i$.

2)

$lt(\tau{ij}) = m_{ji} e_{i}$.

3)

$\{\tau_{ij}\} \cup \{\nu_{ij}\}$ is a standard basis for syz(M) as A-module.

Proof: Again, the main thing to show is that the leading term of an arbitrary syzygy in normal form is divisible by that of a certain STZS-syzygy. Assume $s=\sum_{l=1}^r h_l*e_l$ to be the choosen syzygy of M. Then $\sum_{l=1}^r h_l*g_l\in I*A^n$. Let lt(s)=m*e_i be the leading term of (the normal form of) s with respect to the ordering <₁ on $k[\underline{x}]^r$. We distinguish two cases:

1.

$m*lt(g_i)\in In(I)$. Let f_j be an element of I dividing m*lt(g_i). Then also kgv_ij divides m*lt(g_i) and, hence, $lt(\nu_{ij})$ divides lt(s).

2.

$m*lt(g_i)\not\in In(I)$. There exists at least one other monomial n*e_i' with m*lt(g_i)=n*lt(g_i') and, following the arguments of the proof of the general theorem, one sees that $lt(\tau_{ii'})$ divides lt(s).

For a fast implementation of this algorithm one has to handle the monomial-weighted orderings. These orderings give weights to the elements of the modules of syzygies by multiplying the corresponding components with certain monomials. Consider for example, [MM], 3.4 (ii).

If the ordering on the module checks first the ordering of the involved monomials and then their component, one can go a step further: Let $\tilde{F}$ denote the transformation of a given basis $F=\{\underline{f}\}$ of a module by multiplying all monomials of the i-th component by the monomial lm(g_i) for all i. Then the next statement is more or less self-evident.

Lemma 2..4   The set F is a standard basis of a module with regard to the monomial-weighted ordering <₁ if and only if $\tilde{F}$ is a standard basis in the given ordering <.

Proof: One point to observe is that the map assigning i to the module component of lm(g_i) must be monotone, i.e., it must not disturb the ordering of the monomials. An other is that in monomial-weighted orderings the comparison of monomials precedes that of module components. Therefore, the trick applies only to these orderings.

To implement monomial-weighted orderings this little lemma is very useful since one needs only to replace the ``ones'' of the unit matrix by the corresponding weight monomials in the initial procedure.

We have also experimented with a complete disregard to special orderings and a decision to reduce always by checking divisibility - which was an idea of F. O. Schreyer. This works as one is sure that all reduces to zero, but, in practice a divisibility check applied to all occurring monomials takes more time than a polynomial arithmetic dealing with polynomials as ordered lists.

We observed a great sensitivity against the ordering of the input and have found, for the homogeneous global case, the degree reverse lexicographical ordering beginning with the greater element to be definitively the best choice.

These considerations lead us to the following implementation:

Let S be a standard basis of $I \subseteq K[x]^r = \sum^r_{i=1} K[x]e_i$. We may assume that $L(s) \not\vert$ L(s') for different $s, s' \in S$. Let $q := \char93 S$.

W := Syz$(\bf S)$
INPUT: S, a standard basis
OUTPUT: W, the module of syzygies of S

$W:= \emptyset$
T := initSyz (S)
L := initPairs (T)
WHILE $L \not= \emptyset$ DO

p := (a, b, s) the last element from L
$L := L\backslash \{(a, b, s)\}$
s := spoly(a,b)
h := NF(s|T)
$W := W \cup \{h\}$

END
W := cancelWeightMonomials(W).

T := initSyz$(\bf S)$
INPUT: S, a standard basis $v_1, \ldots, v_s$
OUTPUT: T, the set $[v_1, lm(v_1), 0, \ldots, 0], \ldots, [v_s, 0, \ldots, 0,lm(v_s)]$

i := r; $T := \emptyset$
S := reOrderDegRevLex(S)
WHILE $S \not= \emptyset$ DO

s := the first element from S
i := i+1
$S := S \backslash \{s\}$
s := s + lm(s)e_i
$T := T \cup \{s\}$

END
setSyzygyOrder(r)

Notice that the regularity (see 3.1) does not apply to STZS-algorithm as it requires that the resolution, as a minimal one, does not have constant entres. Then the bound for degrees can be decreased by one in the next module beginning with the highest.

But here, this contradicts the computation of a standard basis which allows only to cancel the whole resolution in a fixed degree. However, we have not found any example where this cancellation gives any advantage.