Refining expression DAGs in exact-decisions number types

Abstract

Exakte Zahlentypen spielen eine zentrale Rolle bei der Entwicklung von robusten Algorithmen in dem Gebiet der Algorithmischen Geometrie, in welchem kombinatorische Entscheidungen auf der Grundlage von numerischen Berechnungen erfolgen. Das „Exact Computation Paradigm“ besagt, dass Robustheit erlangt werden kann, indem sichergestellt wird, dass alle Entscheidungen, die während der Ausführung eines Algorithmus getroffen werden, korrekt sind. In einem Exakte-Entscheidungen-Zahlentyp wird die Berechnung eines Programms in einem gerichteten azyklischen Graphen, einem so genannten arithmetischen Ausdrucksgraphen, abgespeichert. Während eines Entscheidungsprozesses werden alle Operationen in dem Ausdrucksgraphen so lange mit sich erhöhender Genauigkeit ausgewertet, bis eine exakte Entscheidung garantiert werden kann. In der vorliegenden Arbeit wird die Auswertung eines Ausdrucksgraphen für Berechnungen mit großen Graphen oder großer Genauigkeit verbessert. Ausdrucksgraphen mit schlechter Struktur können einen quadratischen Anstieg in der Laufzeit zur Folge haben, wenn die Berechnungen groß werden. Diese Effekte können durch Methoden zum Balancieren von sowohl der verwendeten Fehlerverteilung als auch der Struktur des Graphen abgemildert werden. In beiden Fällen werden optimale Strategien vorgestellt, bewiesen und experimentell ausgewertet. Das Balancieren von Fehlerschranken ist sehr vielseitig einsetzbar und kann einen großen Teil der Kosten, die mit der unbalancierten Struktur verknüpft sind, verringern. Das Anwendungsfeld für die Methode der Neustrukturierung ist eingeschränkter. Wenn sie eingesetzt werden kann, führt dies jedoch häufig zu starken Verbesserungen der Laufzeit. Sowohl Situationen, in denen Neustrukturieren vorteilhaft ist, als auch Situationen, in denen Neustrukturierung nachteilig ist, werden in der Arbeit beschrieben. Sobald eine hohe Genauigkeit erforderlich ist, kann die Laufzeit durch die Parallelisierung der arithmetischen Operationen in dem Ausdrucksgraphen verringert werden. Methoden für eine effektive Parallelisierung werden beschrieben, analysiert und experimentell ausgewertet. Eine Neustrukturierung kann dazu benutzt werden, die Parallelisierbarkeit eines Ausdrucksgraphens zu erhöhen. Beide Balanciermethoden werden im Hinblick auf eine parallele Umgebung ausgewertet.

Exact number types play a central role in the development of robust algorithms in the field of computational geometry, where combinatorial decisions are made on the basis of numerical computations. The Exact Computation Paradigm states that for achieving robustness it is sufficient to guarantee that all decisions made during the execution of an algorithm are correct. In an exact-decisions number type, the computation history of a program is stored in a directed acyclic graph, a so-called arithmetic expression dag. During a decision process, all operations in the expression dag are evaluated with increasing accuracy until an exact decision can be guaranteed. In this work, the evaluation process of an expression dag is improved for computations with large expression dags or high accuracy. Badly structured expression dags can lead to a quadratic increase in the evaluation time if computations get large. These effects are mitigated by balancing methods for both the error distribution appearing during an evaluation and the graph structure itself. In both cases, optimal strategies are proposed, proven and experimentally evaluated. Error bound balancing is very versatile and can reduce a large amount of the cost associated with unbalanced structures. The field of application for restructuring is more narrow, but when it can be used it often leads to strong improvements on the running time. Both situations in which restructuring is beneficial and situations in which restructuring can be detrimental to the running time are described in this work. If a high accuracy is required, the evaluation time can be reduced by a parallelization of the arithmetic operations in the expression dag. Methods for an effective parallelization are described, analyzed and experimentally evaluated. Restructuring can be employed to increase the parallelizability of an expression dag. Both balancing methods are evaluated with respect to a parallel environment.