Next: 2.2 The STZSalgorithm
Up: 2. The ground algorithms
Previous: 2. The ground algorithms
The common algorithm stores the reduction process of a standard basis
computation and obtains in this way a basis for the module of syzygies.
Assume that an Rmodule
is given by the columns of a matrix:
Then we add a new module component to each element of the
given basis. The extra component then notices what happens with its
corresponding element:
After a standard basis computation we obtain a matrix like the right one,
where A' corresponds to the standard basis of A, B' is a transformation
matrix, i.e., A'=A*B' and C' represents a basis of the module syzygies of
A. In fact, every syzygy constitutes a certain way to obtain 0 as linear
combination of the given generators. In this way, we find a basis of all
syzygies. Otherwise a syzygy, which is not included, will
produce elements with new leading terms.
Following this idea we obtain an easy implementation of this algoritm:
W := Syz
INPUT: S, a basis of an ideal
OUTPUT: S' a minimal set of generators; W' the module of syzygies of S'


T := initSyz (S)
T' := std (S)
setRegularity(T')
WHILE
DO

 IF t
is syzygy W := t
T' :=
t
END
(S',W') := minimize(S,W).
T := initSyz
INPUT: S, a standard basis
OUTPUT: T, the set

 i := r;
S := interReduce(S)
WHILE
DO

 s := the first element from S
i := i+1
s := s + e_{i}
END
setSyzygyOrder(r)
minimize
INPUT: S, a basis, W, its syzygies
OUTPUT: S', a minimal system of generators, W', its syzygies

 W' := W
S' := S
WHILE searchUnit(W',i,j) DO

 W' := Gauss(W',i,j)
S' :=
END
In the interreduction we subtract multiples of elements from others as long
as any leading term divides another one. The
interreduction of the input must always precede the adding of new module
components. Otherwise this would result in a much more complicated structure
of the module of syzygies.
In the part of minimization one searches for units of the ground ring
in the entres of the matrix C' corresponding to the syzygies. Then one
performs a Gaussian elimination with the associated row and cancels
the row and the column where the unit was found at the end:
Notice that for each Gaussian elimination one has to multiply all
remaining columns with the unit u_{1} which implies that the length
of all polynomials grows at least by the number
l_{1}=length(u_{1})
of monomials of u_{1}. In the case of global computaions all units are just
constants. However, for local or mixed
orderings these units are polynomials in the non global variables and the
length of the polynomials grows during n Gaussian elemenations by:
where
l_{i}=length(u_{i}) is the number of monomials in the ith unit at the
begin of the minimization. To decrease this growth one might use Bareiss'
algorithm, but this would imply additional polynomial divisions.
Our experience agrees with this observation:
in a nonglobal case it is often the minimization which is the really hard
part to compute a minimal resolution, whereas in the global case it is
always the standard basis.
Next: 2.2 The STZSalgorithm
Up: 2. The ground algorithms
Previous: 2. The ground algorithms
 ZCA Home 
Reports 