next up previous
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 $(K_i)_j$ for any $i=0,\ldots,n$ and $j>0$, 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 $(K_i)_j$ contains $(K_{i-1})_j$ via a subset of generators which is, moreover, a standardbasis of $(K_{i-1})_j$. Further, there is a $k>0$ such that the first $k$ module components (w.r.t. the ordering) correspond exactly to the new generators of $(K_i)_{j-1}$ in the $i$-th subresolution compared with the $(i-1)$-th. Finally, any generator of $(K_i)_j$ is a syzygy of $(K_i)_{j-1}$.

The syzygies of the subset $(K_{i-1})_j$ are computed in the $(i-1)$-th subresolution. Thus, we have to consider only pairs of module elements whose leading term is in the first $k$ components. Let us assume that a reduction of such a pair leads to an element $sp$ with leading term not in these $k$ components. Then it remains, of course, a syzygy of $(K_i)_{j-1}$. Indeed, because of its leading term it is a syzygy of $(K_{i-1})_{j-1}$ and, hence, it lies in $(K_{i-1})_j$. As $(K_{i-1})_j$ is given as a standard basis the reduction could be completed by the computation of the normal form of $sp$ w.r.t. $(K_{i-1})_j$.$\Box$
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 $J_i$. The normal form correspond to the choice of representation of $F_id'_{j+1}(e_s)$.

For the original ideal (or, module) the situation is different: The leading term of the new generators $f_i$ may ly within the given leading ideal (or, module). Thus, generators of the standard basis of $I_{i-1}$ might be reduced by the extension coming from $f_i$. In this case, the generator of the standard basis of $I_{i-1}$ is replaced by its reductum if it is not contained in the set $\{f_1,\ldots,f_n\}$ (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 $I$:

Lemma 5.2   Let $e_i\in R^i$ denote the component assigned to the new generator $f_i$. As soon as the reductum of the s-polynomial $sp$ of an arbitrary pair of elements of $I_i$ has a representation whose leading term is not a multiple of $e_i$, the pair can be skipped from the reduction.

PROOF: When the leading term of the representaion of $sp$ is not a multiple of $e_i$ this means simply $sp\in I_{i-1}$. But, the standard basis of $I_{i-1}$ as well as its syzygies are just computed in the $(i-1)$-th subresolution.$\Box$

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