Next: 6. Timings and Choice Up: Recursive Computation of Free Previous: 4. The Algorithm

# 5. Special Improvements

The sequential algorithm allows some improvements of the reduction procedure in comparison with other implementations of free resolutions.

Lemma 5.1   The computation of a standard basis of any higher syzygy modules, i.e. within for any and , is devided into a standard basis computation on a partial module and the computation of normal forms.

PROOF: Let us look at Figure 4 The module contains via a subset of generators which is, moreover, a standardbasis of . Further, there is a such that the first module components (w.r.t. the ordering) correspond exactly to the new generators of in the -th subresolution compared with the -th. Finally, any generator of is a syzygy of .

The syzygies of the subset are computed in the -th subresolution. Thus, we have to consider only pairs of module elements whose leading term is in the first components. Let us assume that a reduction of such a pair leads to an element with leading term not in these components. Then it remains, of course, a syzygy of . Indeed, because of its leading term it is a syzygy of and, hence, it lies in . As is given as a standard basis the reduction could be completed by the computation of the normal form of w.r.t. .
REMARK:Compared with Chapter 3.3 the computation of the standard basis of the partial module is exactly the computation of the next syzygy module of the resolution of the extension ideal . The normal form correspond to the choice of representation of .

For the original ideal (or, module) the situation is different: The leading term of the new generators may ly within the given leading ideal (or, module). Thus, generators of the standard basis of might be reduced by the extension coming from . In this case, the generator of the standard basis of is replaced by its reductum if it is not contained in the set (which may happen only in the non-homogeneous case).

Moreover, there is a new criterion concerning the dependence from sets of generators for the computation of the standard basis of an ideal :

Lemma 5.2   Let denote the component assigned to the new generator . As soon as the reductum of the s-polynomial of an arbitrary pair of elements of has a representation whose leading term is not a multiple of , the pair can be skipped from the reduction.

PROOF: When the leading term of the representaion of is not a multiple of this means simply . But, the standard basis of as well as its syzygies are just computed in the -th subresolution.

Next: 6. Timings and Choice Up: Recursive Computation of Free Previous: 4. The Algorithm
| ZCA Home | Reports |