Implementierung von kd-Trees für eine "geometrische" Variante des Buchberger-Algorithmus
Hintergrund
Der Buchberger-Algorithmus berechnet Gröbner-Basen von Polynomidealen. Diese sind eine für die Computeralgebra besonders schöne Darstellung, deren Berechnung aber mitunter sehr aufwändig sein kann. Etwas einfacher ist der Fall der torischen Ideale, in welchem alle Polynome nur zwei teilerfremde Terme enthalten. Hier können sämtliche Berechnungen mit den Integervektoren anstelle von ganzen Polynomen durchgeführt werden. Der Buchberger-Algorithmus für diesen Spezialfall wird wegen seiner Anwendungen in der diskreten Optimierung "geometrisch" genannt.
Projekt
Im geometrischen Buchberger-Algorithmus besteht der Hauptaufwand darin, Vektoren in einer größeren Menge zu finden, welche komponentenweise kleiner als ein gegebener Vektor sind. Dies lässt sich als Range-Query in kd-Trees interpretieren und damit gegenüber einer linearen Suche optimieren.
In diesem Projekt sollen kd-Trees und ggf. Varianten implementiert und mit der ursprünglichen Suche an echten Datensätzen verglichen werden. Für den direkten Vergleich ist eine Einbindung in das Softwarepaket 4ti2 wünschenswert, welches die derzeit effizienteste Opensource-Implementierung des geometrischen Buchberger-Algorithmus ist.
Voraussetzungen
- Kentnisse in C++
- Grundlagen: Algorithmen und Datenstrukturen (GAD) und/oder
- Effiziente Algorithmen und Datenstrukturen I (EADS)
Referenzen
Diese Referenzen sind nur geeignet, sich schnell eine Vorstellung von dem Projekt zu machen. Für die Einarbeitung wird detailliertere Literatur empfohlen werden.
- http://en.wikipedia.org/wiki/Kd-tree
- http://en.wikipedia.org/wiki/Buchberger's_algorithm
- http://www.4ti2.de
Kontakt
Bei Interesse wenden Sie sich bitte an Stephan Ritscher.