next up previous
Next: 3. Improvements Up: 2. The ground algorithms Previous: 2.1 The common algorithm

2.2 The STZS-algorithm

Let $S = \{g_1, \ldots, g_q\}$ be a standard basis of $I \subseteq

For $K[x]^q = \sum^{q}_{i=1} K[x] e_i$ we choose the following monomial-weighted ordering <1 (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 gi, gj, 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 (gi, gj) := mjigi - mijgj 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)

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

with L(hij) < 1 if $h_{ij} \not= 0$ and $L(\xi^{ij}_\nu g_\nu) <

For j > i such that gi, gj have leading term in the same component, let

\begin{displaymath}\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 <1 the following holds:

$L(\tau_{ij}) = m_{ji} e_i$.
$\{\tau_{ij} \mid i < j$ s.t. L(gi), L(gj) 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

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

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

with $h_k\in k[\underline{x}]$ and lt(hk*gk)<kgvij*ei. Now, set

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

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

$lt(\nu{ij}) = (kgv_{ij}/m) e_i$.
$lt(\tau{ij}) = m_{ji} e_{i}$.
$\{\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*ei be the leading term of (the normal form of) s with respect to the ordering <1 on $k[\underline{x}]^r$. We distinguish two cases:
$m*lt(g_i)\in In(I)$. Let fj be an element of I dividing m*lt(gi). Then also kgvij divides m*lt(gi) and, hence, $lt(\nu_{ij})$ divides lt(s).
$m*lt(g_i)\not\in In(I)$. There exists at least one other monomial n*ei' with m*lt(gi)=n*lt(gi') 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(gi) 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 <1 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(gi) 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\}$
W := cancelWeightMonomials(W).

T := initSyz$(\bf S)$
S, a standard basis $v_1, \ldots, v_s$
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)ei
$T := T \cup \{s\}$

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.

next up previous
Next: 3. Improvements Up: 2. The ground algorithms Previous: 2.1 The common algorithm
| ZCA Home | Reports |