Forschungsbericht 2012 - Max-Planck-Institut für Informatik

Exaktes geometrisches Rechnen

Autoren
Sagraloff, Michael
Abteilungen
Algorithmen und Komplexität (Kurt Mehlhorn)
Zusammenfassung
Die Forschungsgruppe entwickelt exakte und vollständige Methoden zur Behandlung komplexer geometrischer Objekte, welche die Grundlage vieler geometrischer Algorithmen bilden. Die Algebra stellt mächtige Werkzeuge zur Lösung der entsprechenden Probleme bereit, allerdings leidet ihre Effizienz unter dem hohen Aufwand für die notwendigen symbolischen Operationen. Durch Kombination von Verfahren aus verschiedenen mathematischen Gebieten konnten wir Algorithmen entwickeln, die nur ein Minimum symbolischer Berechnungen benötigen und weitestgehend auf schneller approximativer Arithmetik beruhen.

Einführung

Geometrische Algorithmen spielen eine wichtige Rolle für die Lösung vieler alltäglicher Fragestellungen. Ein klassisches Beispiel ist das sogenannte "Piano Mover's Problem", bei dem es, vereinfacht ausgedrückt, darum geht, durch Berechnung zu entscheiden, ob beim nächsten Umzug das Klavier durch den Treppenaufgang passt. Ein weiterer Anwendungsbereich sind CAD (Computer Aided Design) Verfahren, die bei der Konstruktion und Visualisierung von technischen Bauteilen inzwischen unabdingbar geworden sind. Ein zentrales Problem hierbei ist die Berechnung sogenannter boolescher Operationen von geometrischen Objekten (Abb. 1), wie etwa der "Vereinigung" der Flügel mit dem Rumpf eines Flugzeugs, oder der Schnitt einer Geraden mit einem beliebigen anderen Objekt.

original
Original 1340287439

Alle Verfahren zur Lösung der oben genannten Probleme setzen sich im Wesentlichen aus einem kombinatorischen Teil, also dem eigentlichen Algorithmus, und der Auswertung sogenannter Prädikate zusammen. Das folgende einfache Beispiel soll dies verdeutlichen: Schlägt man Nägel (an vorgegebenen Punkten) zur Hälfte in ein Brett und spannt ein Gummiband um diese Nägel, so berandet das Band die konvexe Hülle der Punkte. Ein einfacher Algorithmus zur Berechnung dieser Hülle basiert auf einer Abfolge von geometrischen Tests, deren Ausgang wiederum die Abfolge beeinflusst. In jedem der Tests werden drei Punkte p, q und r ausgewählt und die Lage von p in Bezug auf die durch q und r verlaufenden Gerade bestimmt. Aus mathematischer Sicht ist eine solche Anfrage gleichbedeutend mit der Bestimmung des Vorzeichens einer von den Eingabepunkten abhängigen Formel F, der sogenannten Prädikatsfunktion. In dem betrachteten Beispiel ist F ein Polynom vom Grad zwei in sechs Variablen, nämlich den Koordinaten der Punkte p, q und r.

Bei der Implementierung eines geometrischen Algorithmus verwendet man aus Effizienzgründen meist approximative Arithmetik zur Auswertung der Prädikatsfunktionen. Als Folge können kleine Rechenungenauigkeiten aufgrund von Rundungsfehlern auftreten. Es besteht der allgemeine Irrglaube, dass diese Fehler das Endresultat nicht sonderlich stark beeinflussen und somit die Verwendung approximativer Arithmetik unproblematisch sei. Tatsächlich treten bereits bei sehr einfachen Verfahren erhebliche Schwierigkeiten auf: So gibt es Konfigurationen, bei denen das Programm vollkommen falsche Resultate liefert, abstürzt oder auch nach beliebig langer Rechenzeit kein Resultat ausgibt. Ein wesentlicher Grund hierfür ist, dass die kombinatorischen Entscheidungen unstetig von den Zwischenergebnissen abhängen, d. h. bereits ein sehr kleiner Fehler kann den Algorithmus auf einen falschen Entscheidungspfad führen. Dies ist in etwa vergleichbar mit dem falschen Abbiegen an einer Kreuzung bei gegebener Wegbeschreibung.

Die Gruppe "Geometric Computing and Computer Algebra" am Max-Planck-Institut für Informatik möchte Lösungen für das oben genannte Problem bereitstellen. Hierbei beschäftigen wir uns vorrangig mit dem algorithmischen Grundgerüst, auf dem die jeweils spezialisierten Lösungsverfahren aufbauen.

Arrangements von algebraischen Kurven und Flächen

Das Grundgerüst der meisten geometrischen Algorithmen bildet die Berechnung von Arrangements. Dabei handelt es sich um eine explizite Beschreibung der Zerlegung der Ebene bzw. des Raumes, die durch gegebene geometrische Objekte induziert wird.

original
Original 1340287455

Objekte von Interesse sind üblicherweise (semi-)algebraische Kurven und Flächen, d. h. die Menge aller Punkte, für die ein System von Polynom(un)gleichungen erfüllt ist. Es ist anzumerken, dass man sich dabei keineswegs nur auf Gleichungen niedrigen Grades beschränken kann, da bereits leichte Problemstellungen auf einfachen geometrischen Objekten die Behandlung schwieriger, gekrümmter Kurven bzw. Flächen voraussetzen. So lässt sich beispielsweise die Menge aller Punkte, die von einer Ellipse einen bestimmten, festen Abstand haben, im Allgemeinen nur durch eine Gleichung 8-ten Grades und einer Reihe zusätzlicher Ungleichungen mathematisch genau beschreiben (Abb. 2).

original
Original 1340287471

Bei der Berechnung von Arrangements in der Ebene stellt die Berechnung der Topologie einer algebraischen Kurve C, welche implizit durch eine Polynomgleichung f(x,y)=0 gegeben ist, einen wichtigen Teilschritt dar. Dabei bestimmt man eine lineare Approximation von C, d. h. eine nur aus Liniensegmenten bestehende Kurve, welche durch kontinuierliches Verformen (ähnlich dem Verformen eines Gummibands) in die ursprüngliche Kurve C überführt werden kann (Abb. 3). Einfache Beispiele zeigen, dass dabei die exakte Ausgangsform der Gleichung f(x,y)=0 zu beachten ist, da bereits kleine Abweichungen zu unterschiedlichen Topologien führen können. Analog zu der topologischen Beschreibung von ebenen Kurven, wird die Topologie einer Fläche F in 3D durch eine entsprechende Triangulierung angegeben, d.h. eine aus Dreiecken bestehende Approximation von F, die durch Deformation in F überführt werden kann.

Exaktheit und Vollständigkeit vs. Effizienz

Die von uns entwickelten Verfahren kommen grundsätzlich mit folgenden zusätzlichen Garantien: Es können alle möglichen Eingaben verarbeitet werden (Vollständigkeit), und das ausgegebene Resultat ist mathematisch korrekt (Exaktheit). Ein wichtiges Forschungsziel ist es dabei, den Brückenschlag zwischen Theorie und Praxis zu schaffen. Das bedeutet, dass neben den theoretischen Zielen wie Vollständigkeit, Exaktheit oder eine geringe asymptotische Komplexität, die Realisierbarkeit einen wichtigen Stellenwert einnimmt. Auch aus diesem Grund werden die von uns entwickelten Methoden im Normalfall implementiert und in große open-source Bibliotheken wie CGAL (Computational Geometry Algorithms Library) integriert. Die bisherigen Ergebnisse zeigen deutlich, dass diese Zielsetzungen keinen Widerspruch darstellen. Vielmehr gehen der Entwicklung theoretisch schneller Algorithmen häufig Erkenntnisse voraus, die in der Praxis gewonnen wurden. Insofern ist es auch nicht verwunderlich, dass praktische und theoretische Effizienz für viele Problemstellungen im Einklang realisierbar sind. Der folgende Abschnitt skizziert, inwiefern sich durch den Einsatz entsprechender Werkzeuge aus verschiedenen mathematischen Gebieten, wie der Numerik, der Computer Algebra und der algebraischen Geometrie, eine vollständige und exakte Berechnung von Arrangements effizient realisieren lässt.

Hybride Verfahren

Bei der exakten Behandlung gekrümmter Objekte müssen Lösungen zu algebraischen Gleichungssystemen gefunden und weiterverarbeitet werden. Die Mathematik, insbesondere die Algebra, stellt hierfür entsprechende theoretische Verfahren bereit, die das exakte Rechnen mit Wurzeln bzw. mit allgemeinen algebraischen Zahlen erlauben. Ein wesentlicher Nachteil dieser Methoden ist, dass die dabei erzeugten Ausdrücke zur Enkodierung der Zwischenergebnisse bereits nach wenigen Schritten sehr kompliziert werden. Folgt man also auf naiver Weise diesem Ansatz, so erkauft man sich Vollständigkeit und Exaktheit mit einer deutlichen Verschlechterung der Laufzeit. Dies gilt insbesondere im Vergleich zu Verfahren, die nur mit numerischen Approximationen rechnen. Aus diesem Grund vertraut man in kommerziellen Systemen ausschließlich auf den Einsatz solcher approximativer Verfahren und nimmt mögliche negative Auswirkungen billigend in Kauf. Will man allerdings Exaktheit und Vollständigkeit gewährleisten, so sind bestimmte symbolische, exakte Operationen, wie etwa die Berechnung des größten gemeinsamen Teilers (ggT) zweier Polynome oder deren Resultante, unvermeidbar. Die Leistungsfähigkeit eines exakten Algorithmus hängt somit entscheidend davon ab, inwiefern solche Operationen effizient implementiert und, vor allem, sparsam eingesetzt wurden.

original
Original 1340287490

Bei der Umsetzung von exakten, symbolischen Berechnungen setzt die Forschungsgruppe auf modulare divide-and-conquer Methoden aus der Computeralgebra. Dabei werden die Berechnungen in viele Einheiten von deutlich niedrigerer Komplexität zerlegt und die Einzelergebnisse schließlich zu einer Gesamtlösung zusammengesetzt. Vorteile dieser Methode sind, dass nahezu alle Berechnungen mit kleinen Zahlen (innerhalb eines Restklassenrings Zp), also innerhalb der Präzision der von der Hardware nativ bereitgestellten Fließkommaarithmetik, durchgeführt werden können und die Methode zudem eine starke Parallelisierung erlaubt. Durch die Verwendung massiv paralleler Hardwarearchitektur, wie sie beispielsweise auf modernen Graphikkarten (GPU) vorzufinden ist, ist es uns gelungen [1] einige wichtige symbolische Berechnungen (Resultanten, ggT) um ein Hundertfaches gegenüber den schnellsten, verfügbaren Implementierungen zu beschleunigen. Dabei handelt es sich nicht ausschließlich um eine naive Umsetzung der oben beschriebenen divide-and-conquer Methode unter Verwendung modularer Arithmetik, sondern vielmehr um ein neues Verfahren, das sowohl der speziellen theoretischen Fragestellung, als auch der speziellen Architektur der GPU gerecht wird. Darüber hinaus haben wir neue Algorithmen zur Berechnung von Arrangements [2–4] entwickelt, die nur auf solchen symbolischen Operationen basieren, welche vollständig auf die GPU ausgelagert werden können. Unter zusätzlicher Verwendung entsprechender theoretischer Resultate (z. B. aus der Algebraischen Geometrie), kann man zeigen, dass sich auf diesem Wege bereits genug "strukturelle Information" gewinnen lässt, so dass alle weiteren Berechnungen ausschließlich approximativ durchgeführt werden können. Beispielsweise müssen in einem Teilschritt des betrachteten Algorithmus zur Berechnung von ebenen Arrangements die Nullstellen eines Polynoms bestimmt werden, dessen Koeffizienten komplizierte algebraische Zahlen sind. Kennt man nun bereits die Gesamtzahl an Nullstellen aufgrund einer Vorberechnung, so lassen sich diese Nullstellen ausschließlich unter Verwendung approximativer Arithmetik bestimmen. Dieser Ansatz erweist sich als deutlich effizienter als die Verwendung eines Verfahrens, das auf exakten Operationen mit den Koeffizienten basiert. Die von uns entwickelten Algorithmen und Implementierungen zur Berechnung von Arrangements in 2D und 3D setzen weltweit Maßstäbe (Abb. 4). So ist es uns durch den Einsatz der oben beschriebenen hybriden Methoden erstmalig gelungen, die Konkurrenzfähigkeit exakter Verfahren gegenüber rein numerischen Methoden, welche keinerlei Zusatzgarantien liefern, nachzuweisen.

Schließlich beschäftigen wir uns auch mit der Entwicklung neuer effizienter Verfahren zur Lösung klassischer, fundamentaler Probleme, wie etwa dem Auffinden und dem Approximieren von Nullstellen eines Polynoms oder dem Lösen eines polynomiellen Gleichungssystems. Unser Interesse an diesen Verfahren ergibt sich auf natürliche Weise aus der Tatsache, dass die entsprechenden Fragestellungen die molekularen Bausteine aller geometrischen Algorithmen bilden. Dabei haben wir erstmalig praktische, einfache und effiziente Verfahren entwickelt, die die besten theoretischen Schranken für die Komplexität dieser Probleme einstellen [5–7] bzw. deutlich verbessern [8,9]. Dieser Beitrag ist insofern als fundamental zu betrachten, da die Vielzahl aller theoretisch schnellen Algorithmen aus der Computeralgebra bzw. Numerischen Analysis sich bisher als nicht sonderlich praxistauglich erwiesen haben.

Basierend auf den bisher gewonnen Erkenntnissen und Erfahrungen sind wir zuversichtlich, dass sich die oben beschriebenen hybriden Ansätze auch als erfolgreich in der Behandlung höherdimensionaler Fragestellungen erweisen werden.

1.
Emeliyanenko; P.
Modular Resultant Algorithm for Graphics Processors
Algorithms and Architectures for Parallel Processing, 427-440 (2010) Best Paper Award
2.
Berberich, E.; Emeliyanenko, P.; Kobel, A.; Sagraloff, M.
Arrangement Computation for Planar Algebraic Curves
Symbolic Numeric Computation, 88-99 (2011)
3.
Berberich, E; Emeliyanenko, P.; Sagraloff, M.
An Elimination Method for Solving Bivariate Polynomial Systems: Eliminating the Usual Drawbacks
Algorithm Engineering and Experiments, 35-47 (2011)
4.
Berberich, E.; Kerber, M.; Sagraloff, M.
An Efficient Algorithm for the Stratification and Triangulation of an Algebraic Surface
Computational Geometry: Theory and Application 43, 257-278 (2010)
5.
Kerber, M.; Sagraloff, M.
Efficient Real Root Approximation
International Symposium on Symbolic and Algebraic Computation, 209-216 (2011)
6.
Sagraloff, M.
A General Approach to Isolating Roots of a Bitstream Polynomial
Mathematics in Computer Science 4, 481-506 (2010)
7.
Sagraloff, M.
When Newton meets Descartes: A Simple and Fast Method to Isolate the Real Roots of a Polynomial
International Symposium on Symbolic and Algebraic Computation 2012; ArXiv:1109.6279v1 (2011)
8.
Emeliyanenko, P.; Sagraloff, M.
On the Complexity of Solving a Bivariate Polynomial System
International Symposium on Symbolic and Algebraic Computation 2012; Arxiv:1104.4954v1 (2011)
9.
Kerber, M.; Sagraloff, M.
Worst-case Bound for Topology Computation of Algebraic Curves
Journal of Symbolic Computation 47, 239-258 (2012)
Zur Redakteursansicht