Signature-based algorithms to compute standard bases

  • 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, Faugère 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 Faugère’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.

Volltext Dateien herunterladen

Metadaten exportieren

  • Export nach Bibtex
  • Export nach RIS

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar
Verfasserangaben:Christian Eder
URN (Permalink):urn:nbn:de:hbz:386-kluedo-29756
Betreuer:Gerhard Pfister
Sprache der Veröffentlichung:Englisch
Veröffentlichungsdatum (online):13.04.2012
Jahr der Veröffentlichung:2012
Veröffentlichende Institution:Technische Universität Kaiserslautern
Titel verleihende Institution:Technische Universität Kaiserslautern
Datum der Annahme der Abschlussarbeit:13.04.2012
Datum der Publikation (Server):16.04.2012
Fachbereiche / Organisatorische Einheiten:Fachbereich Mathematik
DDC-Sachgruppen:5 Naturwissenschaften und Mathematik / 51 Mathematik / 512 Algebra
MSC-Klassifikation (Mathematik):13-XX COMMUTATIVE RINGS AND ALGEBRAS / 13Pxx Computational aspects and applications [See also 14Qxx, 68W30] / 13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
Lizenz (Deutsch):Standard gemäß KLUEDO-Leitlinien vom 15.02.2012

$Rev: 13581 $