For we choose the following monomial-weighted ordering <_{1} (depending on S): if and only if either or and i > j.
For g_{i}, g_{j}, having the leading term in the same component, that is we consider spoly (g_{i}, g_{j}) := m_{ji}g_{i} - m_{ij}g_{j} with .
Because S is a standard basis we obtain ([SI], Corollary 1.11)
For j > i such that g_{i}, g_{j} 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.
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.
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(g_{i}) for all i. Then the next statement is more or less self-evident.
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
INPUT: S, a standard basis
OUTPUT: T, the set
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.