4. The Algorithm

The implementation of the ideas of the preceding Chapter is realized as $SMO$-algorithm in the terminology of Chapter 2. After the sequence of generators we use secondly the module index and than, thirdly, the degree of the lowest common multiples of the pairs as ordering criteria on the pair sets.

Within the computation of free resolutions each new generator (which is either a polynomial from the input or a syzygy of certain generators) is equipped with a unique module component which stores the reduction performed with this generator. Moreover, the assigned module components are the basing units for the syzygies. The relation of the ordering of generators and that of their corresponding components is very sensible. Our practical experience indicates that the orderings introduced by F.-O. Schreyer (see [6]) are the best choice for computations of free resolutions.

Here, we have to use another class of orderings:

Definition 4.1   Assume that the ordering $<$ on $R^p$ fulfils either:

$$i<j\ \longrightarrow\ me_i<m'e_j$$

or

$$i<j\ \longrightarrow\ me_i>m'e_j$$

for any $\{me_i,m'e_j\}\subset R^p$. Such an ordering is called a sequential monomial ordering if it agrees with the addition of new elements within an algorithm to compute free resolutions, i.e., module components assigned to new generators are greater w.r.t. $<$ than all the former components.

REMARK:The definition requires to give new generators greater components for the first and smaller components for the second variant. Note that the definition is restricted to only 2 possible variants. In general any ordering for which new generators have components greater than all former are working.
In the sequel we always assume to work with the first sequential ordering from the definition.

Now, we describe the several steps of a sequential algorithm for an ideal $I=(f_1,\ldots,f_n)\subset R$:

1. We start with index $i=1$.
2. We increase $i$ and return the result if $i=n+1$.
3. We normalize the generator $f_i$ with respect to the ideal $I_{i-1}$. If $Normalform(f_i)\not=0$ we put it to the set of generators and compute a standardbasis of $I_i$ as well as of the syzygies of $I_i$.
4. We decide wether $Normalform(f_i)$ yields a regular extension by the criteria of the Chapter 3.1. If so, we go to the next step. If not, we skip the next step.
5. We are in the case of a regular extension. We copy the resolution of $I_{i-1}$ and the mappings $F_i$ as multiplications with $Normalform(f_i)$. Now, we are going back to step 2.
6. We are in the case of a non-regular extension. We initialize an inner loop over the module index starting with 0.
7. We are going to the next module. If there are no new generators we return to step 2. If there are new generators, we assign new module components to the new generators and add them to the known generators.
8. We perform a standard basis computation on all pairs build from the new generators. With the new syzygies we go back to the step 7.

The recursion step of the algorithm can be visualized by the following figures (for a proof see Lemma 5.1): The first figure shows the resolution after the $(i-1)$-th step.

Figure 1: (i-1)-th subresolution

The $j$-th block of this figure shows the size of the matrix of the $j$-th map in the $(i-1)$-th subresolution. Therefore, the hight of the $j$-th block is equal to the length of the $(j-1)$-th block. The situation after the computation of the $i$-th subresolution is shown in Figure 2.

Figure 2: i-th subresolution

The old figure corresponds to the empty blocks. In the first matrix a new column is added for the new generator $f_i$. Corresponding to this the second matrix has one new row (vertically hatched). Analogously, any higher matrix contains as many more new generators (horizontally hatched) as the next matrix new rows (vertically hatched). Further, the vertically hatched blocks of index $>0$ correspond to a free resolution of the $i$-th extension ideal $J_i$, whereas, the horizontally hatched blocks correspond to the representations chosen in Lemma 3.6.

If the $i$-th extension is regular the horizonally hatched blocks can be chosen as identical copies of the $(i-1)$-th subresolution with index shifted by 1. Thus, if all matrices of the $(i-1)$-th subresolution are given as standard bases the $i$-th subresolution consists of standard bases, too.

The algorithm is implemented in SINGULAR realizing the following pseudo code: $L_* :=$ Res$(\bf I)$
INPUT: $I=(f_1,\ldots,f_n)$, a basis of an ideal
OUTPUT: $L_*$ a resolution of $R/I$;

$i:=0$;
$I_0:=(0)$;
WHILE $i<n$ DO

$i:=i+1$;
$f_i$:=Normalform($f_i$,$I_{i-1}$);
IF $f_i\not= 0$ DO

$I_i:=I_{i-1}+(f_i)$;
IF $is\_regular\_extension(f_i,I_{i-1},I_i)$ DO

$K_i$:=Koszul_extension($K_{i-1}$,$f_i$);

ELSE

WHILE $(K_i)_j\not=(K_{i-1})_j$ DO
. $(K_i)_{j+1}:=reduce\_new\_generators((K_i)_j)$
OD

FI

FI

OD
$L_*:=K_n$