Next: 5. Special Improvements
Up: Recursive Computation of Free
Previous: 3.3 Nonregular Extensions
4. The Algorithm
The implementation of the ideas of the preceding Chapter is realized
as 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
fulfils either:
or
for any
. 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
:
 We start with index .
 We increase and return the result if .
 We normalize the generator with respect to the ideal .
If
we put it to the set of generators and
compute a standardbasis of as well as of the syzygies of .
 We decide wether
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.
 We are in the case of a regular extension. We copy the resolution
of and the mappings as multiplications with
. Now, we are going back to step 2.
 We are in the case of a nonregular extension. We initialize an
inner loop over the module index starting with 0.
 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.
 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 th step.
Figure 1:
(i1)th subresolution

The th block of this figure shows the size of the matrix of the th
map in the th subresolution. Therefore, the hight of the th block
is equal to the length of the th block. The situation after the
computation of the th subresolution is shown in Figure 2.
Figure 2:
ith subresolution

The old figure corresponds to the empty blocks. In the first matrix a new
column is added for the new generator . 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 correspond to a free resolution of the th extension ideal
, whereas, the horizontally hatched blocks correspond to the
representations chosen in Lemma 3.6.
If the th extension is regular the horizonally hatched blocks can be
chosen as identical copies of the th subresolution with index shifted
by 1. Thus, if all matrices of the th subresolution are given as
standard bases the th subresolution consists of standard bases, too.
The algorithm is implemented in SINGULAR realizing the following
pseudo code:
Res
INPUT:
, a basis of an ideal
OUTPUT: a resolution of ;
 ;
;
WHILE DO
 ;
:=Normalform(,);
IF DO

;
IF
DO
 :=Koszul_extension(,);
ELSE
 WHILE
DO
.
OD
FI
FI
 OD
Next: 5. Special Improvements
Up: Recursive Computation of Free
Previous: 3.3 Nonregular Extensions
 ZCA Home 
Reports 