Algebra Seminar talk
2021-04-30
Patrick Freund
Gröbnerbasen und der Buchberger-Algorithmus
Abstract:
Ein Teil der kommutativen Algebra ist der algorithmische/rechnerische Aspekt,
in dem man aus einer Existenzaussage eine Methode zur Konstruktion ableitet.
Ein typisches Beispiel wäre der Hilbert'sche Basissatz, dessen Aussage die
Existenz einer endlichen Basis eines Ideals ist. Wie man zu so einer Basis
kommt, geht aus dem ursprünglichen Beweis von Hilbert nicht hervor. Die Suche
nach einer Konstruktion ist Teil der algorithmischen kommutativen Algebra.
In diesem Vortrag widme ich mich diesem algorithmischen Teil der kommutativen Algebra, also Berechnungsmethoden. Als Aushängeschild hierfür wählte ich die Gröbnerbasen und den darauf aufbauenden Buchberger-Algorithmus.
Eine Gröbnerbasis ist eine Basis eines Ideals des Polynomrings mit einer oder mehreren Unbekannten. Durch die Bestimmung so einer Basis erhält man ein Verfahren zur Feststellung der Idealzugehörigkeit.
Hierfür wird die sogennante Normalformabbildung eingeführt, die man gewissermaßen als den Rest modulo dem Ideal sehen kann. Sofern dieser Rest gleich 0 ist, ist die Zugehörigkeit zum Ideal sichergestellt. Diese Abbildung ist wohldefiniert für Gröbnerbasen, da die Normalform eines Polynoms bezüglich Gröbnerbasen eindeutig definiert ist.
Hat man es mit einem System von Polynomgleichungen zu tun, genügt es eine Basis des Ideals zu betrachten, das durch die vorgegebenen Polynome erzeuget wird. Zur Lösung des Systems dienen nun die Basispolynome, die vorteilshafterweise eine geringere Anzahl an Variablen und niedrigere Polynomgrade vorweisen.
Der Buchberger-Algorithmus zur Bestimmung einer Gröbnerbasis ist demnach eine Verallgemeinerung der berühmten Algorithmen von Gauß und Euklid.