3.2 Direct minimizations

One possibility to speed up the common algorithm is obtained by using information from the standard basis computation directly to minimize the input. One knows about elements not belonging to a minimal basis as they are used multiplied only with a constant, but not with a proper monomial somewhere in the reduction. If this happens one has, moreover, two elements of the module or ideal having the same leading term. By exchanging both we take out the superfluous generator and if the reduction of the spolynomial yields zero, we skip the corresponding syzygy. Otherwise we think of the remaining polynomial as a new generator.

To implement this we have to rewrite the normal form procedure in the following manner:

$g={\bf NF}(f,F)$
INPUT: $F=\{g_1,\ldots,g_n\}$ generators of the given ideal, f a spolynomial
OUTPUT: the normal form of f with respect to F

exchanged:=FALSE
while $S:=\{f_i\in F\vert lt(f_i)\vert lt(g)\}\not=\emptyset$

if ( $\exists f_i\in input : lt(f_i)=c*lt(g)$) and not exchanged

h:=f_i
f_i:= g
$input:=input\setminus \{f_i\}$
exchanged:=TRUE

else choose $h\in S$ w.r.t. the strategy
g:=spoly(g,h)

if exchanged

if $g\in syz(input)$

g:=0

else

renew(g)
$F:=F\setminus\{f_i\vert f_i$ was reduced with $h\}$

In the case of global homogeneous computations it easy to organize the algorithm in such a way that no generator which occur in a direct reduction was used before. The simple solution is to compute degree by degree.

For local computations a more sophisticated strategy is necassary. One computes again degree by degree with respect to the leading terms. But, whenever the degree changes, one has to use a lazy strategy, which means to continue with the other pairs of same degree first. Usually direct reductions are to prefer for any other kind of reductions, even with bad eca1are preferred for any other kind of reductions, even with bad ecart. Our experiences show that it is advisable to keep back multiples of elements with good ecart if they are destroyed by direct reductions.

The optimal effect of the direct reductions may be obtained applying a technique of R. LaScala [LS], which uses the fact that a syzygy produced as reduction of an spolynomial and the reductum (if it is not 0) not survives in the minimized complex. Hence, there is no need to equip this syzygy with a component in the next computation.