Signature-based algorithms to compute standard bases
Christian Eder · Publication Server of Kaiserslautern University of Technology (Kaiserslautern University of Technology) · 2012
Standard bases are one of the main tools in computational commutative algebra. In 1965 Buchberger presented a criterion for such bases and thus was able to introduce a first approach for their computation. Since the basic version of this algorithm is rather inefficient due to the fact that it processes lots of useless data during its execution, active research for improvements of those kind of algorithms is quite important. In this thesis we introduce the reader to the area of computational commutative algebra with a focus on so-called signature-based standard basis algorithms. We do not only present the basic version of Buchberger’s algorithm, but give an extensive discussion of different attempts optimizing standard basis computations, from several sorting algorithms for internal data up to different reduction processes. Afterwards the reader gets a complete introduction to the origin of signature-based algorithms in general, explaining the under- lying ideas in detail. Furthermore, we give an extensive discussion in terms of correctness, termination, and efficiency, presenting various different variants of signature-based standard basis algorithms. Whereas Buchberger and others found criteria to discard useless computations which are completely based on the polynomial structure of the elements considered, Faugere presented a first signature-based algorithm in 2002, the F5 Algorithm. This algorithm is famous for generating much less computational overhead during its execution. Within this thesis we not only present Faugere’s ideas, we also generalize them and end up with several different, optimized variants of his criteria for detecting redundant data. Being not completely focussed on theory, we also present information about practical aspects, comparing the performance of various implementations of those algorithms in the computer algebra system Singular over a wide range of example sets. In the end we give a rather extensive overview of recent research in this area of computational commutative algebra.