Gröbnerbasenberechnung mit flexiblen Polynomdarstellungen
Softwaretechnik-Praktikum im Sommersemester 2003
Universität des Saarlandes – Informatik
Informatik Campus des Saarlandes
Campus E9 1 (CISPA)
66123 Saarbrücken
E-mail: zeller @ cs.uni-saarland.de
Telefon: +49 681 302-70970
Beschreibung
Für viele Anwendungen der Computeralgebra sind Gröbnerbasen eine essentielle Hilfe. Mit Ihrer Hilfe lassen sich polynomielle Gleichungssystem lösen bzw. deren Unlösbarkeit beweisen, Dimension von Lösungsräumen bestimmen, und, wenn prinzipiell möglich, die Lösungen parametrisieren.Leider hat die Theorie auch einen Haken: Im Allgemeinen ist es sehr aufwändig, Gröbnerbasen zu berechnen. Es liegen zwar theoretische Ergebnisse zur Komplexität vor, diese spiegeln aber die Anwendungsrealität nicht wider.
Der übliche Algorithmus für diese Aufgabe ist der Buchberger-Algorithmus, den wir im Praktikum genauestens beleuchten wollen. Dieser Algorithmus nimmt eine Menge von Polynomen und fügt ihr Kombinationen von Vielfachen der Polynome hinzu, bis die Menge bestimmte Kriterien erfüllt, die eine Gröbnerbasis ausmachen. Der Algorithmus ist recht kurz und nicht schwierig zu verstehen. In einem zweiten Schritt berechnen wir aus der Gröbnerbasis mit Hilfe von Schreyers Algorithmus eine Hilbertauflösung, die der Startpunkt vieler fundamentaler Algorithmen der Computeralgebra ist.
Wir wollen im Praktikum eine Testumgebung bauen, mit der wir untersuchen können, an welchen Stellen in diesen Algorithmen wieviel Zeit verbraucht wird. Die Polynome wollen wir dabei auf unterschiedliche Weisen implementieren und experimentell ermitteln, welche Polynomdarstellung für den Buchberger-Algorithmus und den Schreyer-Algorithmus bei relevanten Beispielen aus der Praxis die günstigste ist.