Diplom-/Bachelor- /Masterarbeit

"Lineare Algebra Ansätze für die effiziente Berechnung von Gröbnerbasen"


Allgemeine Beschreibung und Ziele:


Zahlreiche Probleme in der Wissenschaft und der Industrie (insbesondere geometrische Probleme, z. B. inverses kinematisches Problem für einen Roboter oder Feststellung der Proteinfunktionen aus der geometrischen Form der Moleküle) lassen sich auf die Lösung algebraischer Gleichungssysteme reduzieren. Im Gegensatz zu linearen Gleichungssystemen, für die wohlbekannte Lösungsverfahren mit  linearen bis kubischen Laufzeiten seit Jahrhunderten existieren, wurde ein Algorithmus für die Analyse und Lösung nichtlinearer Gleichungssysteme erst vor ca. 40 Jahren entdeckt (Buchberger-Algorithmus). Das zentrale Element dabei ist der Begriff der Gröbnerbasis. Wie von E. Mayr und A. Meyer gezeigt wurde, kann die Laufzeit der Gröbnerbasenberechnung im Worst Case doppeltexponentiell in Abhängigkeit von der Anzahl der Variablen steigen, was bestimmte Gleichungssysteme unlösbar macht. Allerdings scheinen  solche doppeltexponentiell wachsende Berechnungskosten nur für bestimmte „pathologische“ Fälle vorhanden zu sein. Man hofft nämlich, dass viele praxisrelevante Probleme sich viel effizienter behandeln lassen, vorausgesetzt, eine effiziente Implementierung des modifizierten Buchberger-Algorithmus ist vorhanden.Das Ziel dieser Arbeit ist die Weiterentwicklung bereits vorhandener Software, und, insbesondere, die Konzeption möglichst effizienter Implementierung eines modernen Ansatzes für Gröbnerbasenberechnung, der auf der Linearen Algebra basiert, und sich aufgrund zu groß werdender Matrizen nicht direkt implementieren lässt.

Aufgabensteller:

Prof. Dr. Ernst W. Mayr

Betreuer:

Dmytro Chibisov    

Genaue Beschreibung der Ziele:

Ähnlich wie die Gausssche Eliminationsprozedur im Falle linearer Gleichungen, eliminiert auch der Buchberger-Algorithmus die Unbekannten, indem bestimmte Operationen mit Termen und Koeffizienten für je zwei Polynome durchgeführt werden. Die ursprünglichen sowie resultierenden Polynome werden gespeichert und immer neue Paare von Polynomen werden iterativ solange gebildet, bis die gespeicherten Polynome eine Gröbnerbasis bilden.Man kann allerdings zeigen, dass erstens die Reihenfolge der Betrachtung der Paare kritisch für die Laufzeiten des Verfahrens ist und zweitens der größte Anteil der Paare,mit denen man rechnet, überflüssig ist, sodass die Prozessorzeit umsonst verschwendet wird(so genannte Reduktionen zu Null). Heutzutage ist man weit davon entfernt, die optimale Reihefolge der Berechnungen mit vertretbaren Kosten berechnen zu können. Allerdings wurden einige heuristische Strategien vorgeschlagen, die in vielen Fällen zur deutlichen Effizienzsteigerung führen.Was das Problem der Erkennung der überflüssigen Berechnungen betrifft, wurden vor kurzem einige interessante Ideen für die effiziente Gröbnerbasenberechnung vorgeschlagen, die auf der Linearen Algebra basieren (ursprünglich eingeführt von Lazard, und später modifiziert und realisiert in so genannten Faugere-Algorithmen F4 and F5).  Indem man das Problem der Gröbnerbasenberechnung geschickt auf die Triangulierung bestimmter Matrizen transformiert, wird es möglich die überflüssigen Berechnungen zu vermeiden. Jedoch führt die Senkung der Berechnungszeit auf diese Art zum Wachstum des notwendigen Speicherplatzes, denn die Matrizen werden zu groß und überschreiten schnell jede vorhandene Speicherkapazität. Der Ausweg bietet sich in der Kompression der Matrizen. Die Matrixkompression in einer oder anderen Form reduziert den notwendigen Speicherplatz, macht den Algorithmus jedoch komplizierter. Um den Lineare Algebra Ansatz zu bewerten und einen vernünftigen Kompromiss zwischen Speicher- und Prozessorzeitverbrauch zu erreichen, soll in der Diplomarbeit dieser Ansatz implementiert werden. Dabei wird der Wert insbesondere auf spezielle Formen der Matrizen gelegt, die bei Behandlung verbreiteter praxisrelevanter geometrischer Probleme entstehen.Nach der Evaluierung und Entwurf der Datenstrukturen und Algorithmen für effiziente Lineare Algebra soll zuerst die vorhandene Gröbnerbasen-Software in C++ unter der Berücksichtigung neuer Ansätze erweitert werden. Damit können im abschließenden Teil der Arbeit experimentelle Berechnungen durchgeführt und Laufzeitergebnisse mit verbreiteter Software für Gröbnerbasen  (z.B. Maple oder CoCoA) verglichen werden. Die besonders reizvolle Herausforderung kann dabei sein, zum Beispiel, nicht nur zu versuchen, existierende Systeme im Bezug auf die Laufzeit zumindest für spezielle Beispiele zu schlagen, sondern vielmehr einige Probleminstanzen zu berechnen, die bis jetzt wegen der oben erklärten Effizienzhindernisse von niemandem berechnet werden konnten.    

Voraussetzungen:

Interesse an mathematischen Fragestellungen und Algorithmen.
Erfahrung mit C/C++ und Computer Algebra Systemen (z.B. Maple) vorteilhaft, aber nicht zwingend.