Next: 2. Sequential Algorithms Up: Recursive Computation of Free Previous: Recursive Computation of Free

# 1. Introduction

The computation of syzygies and free resolutions of ideals and modules is one of the main applications of computer algebra. It is common folklore that a Groebner basis computation produces also all information about the module of syzygies of a set of generators. First implementations of free resolutions were based on this fact. In the last years several improvements of this approach were developped and implemented (see [5], [1] and [7]). The main ideas of these improvements are special reduction strategies based on F.-O. Schreyer´s monomial orderings and the usage of the Hilbert function to avoid useless pairs within the reduction process. All these algorithms use the traditional process of creating s-polynomials of pairs of polynomials and reducing them.

In abstract algebra there is another idea to compute free resolutions of ideals - the Koszul complex (see J.L. Koszul [4]). Its commutative variant is based on the concept of regular sequences of elements of a ring (see Chapter 17 of [3]).

In this paper we connect the ideas used in the Koszul complex with the computation of free resolutions based on Buchberger's algorithm. For this purpose the notion of a sequential algorithm is introduced in chapter 2. This kind of algorithm constructs the free resolution of an ideal via a sequence of subideals (which differ by one generator each time) and the extension of the associated free resolutions. Along this line we decide first the -regularity of a new generator and use a tensor product of complexes in the positive case. The key-point of the algorithm is the handling of the non--regular generators. In Chapter 3.3 we construct a natural generalization of the Koszul complex for non--regular generators (which should not be confused with the generalized Koszul complex introduced by D. Buchsbaum [2]). This construction might give a deeper insight into the nature of free resolutions.

The algorithmic part of this new construction is mainly done by a special choise of orderings on the resolution which allows to put the different cases in a natural framework (see Chapter 4). Finally, the pseudo code of such an algorithm is presented and we give some timings based on an implementation within the computer algebra system SINGULAR.

Next: 2. Sequential Algorithms Up: Recursive Computation of Free Previous: Recursive Computation of Free
| ZCA Home | Reports |