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

## 2.2 The STZS-algorithm

Let be a standard basis of .

For we choose the following monomial-weighted ordering <1 (depending on S): if and only if either or and i > j.

For gi, gj, having the leading term in the same component, that is we consider spoly (gi, gj) := mjigi - mijgj with .

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

with L(hij) < 1 if and .

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

Let ker denote the module of syzygies, syz(I), of . 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:

1)
.
2)
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 be the factor of a polynomial ring after a certain ideal and let 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 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 in normal form with respect to I is divisible by some leading term lt(g) for .

Assume and lt(gi)=m*ei. Denote by kgvij the lowest common multiple of m and lt(fj). Then and, therefore, (G is standard basis!):

with and lt(hk*gk)<kgvij*ei. Now, set

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

1)
.
2)
.
3)
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 to be the choosen syzygy of M. Then . Let lt(s)=m*ei be the leading term of (the normal form of) s with respect to the ordering <1 on . We distinguish two cases:
1.
. Let fj be an element of I dividing m*lt(gi). Then also kgvij divides m*lt(gi) and, hence, divides lt(s).
2.
. 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 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 denote the transformation of a given basis 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 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 . We may assume that L(s') for different . Let .

W := Syz
INPUT: S, a standard basis
OUTPUT: W, the module of syzygies of S

T := initSyz (S)
L := initPairs (T)
WHILE DO
p := (a, b, s) the last element from L

s := spoly(a,b)
h := NF(s|T)
END
W := cancelWeightMonomials(W).

T := initSyz
INPUT:
S, a standard basis
OUTPUT:
T, the set

i := r;
S := reOrderDegRevLex(S)
WHILE DO
s := the first element from S
i := i+1

s := s + lm(s)ei
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.

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