Loading…
Locally solving linear systems for geometry processing
Herholz, Philipp
Geometry processing algorithms commonly need to solve linear systems involv- ing discrete Laplacians. In many cases this constitutes a central building block of the algorithm and dominates runtime. Usually highly optimized libraries are em- ployed to solve these systems, however, they are built to solve very general linear systems. I argue that it is possible to create more efficient algorithms by exploit- ing domain knowledge and modifying the structure of these solvers accordingly. In this thesis I take a first step in that direction. The focus lies on Cholesky fac- torizations that are commonly employed in the context of geometry processing. More specifically I am interested in the solution of linear systems where variables are associated with vertices of a mesh. The central question is: Given the Cholesky factorization of a linear system defined on the full mesh, how can we efficiently ob- tain solutions for a local set of vertices, possibly with new boundary conditions? I present methods to achieve this without computing the value at all vertices or refactoring the system from scratch. Developing these algorithms requires a de- tailed understanding of sparse Cholesky factorizations and modifications of their implementation. The methods are analyzed and validated in concrete applica- tions. Ideally this thesis will stimulates research in geometry processing and re- lated fields to jointly develop algorithms and numerical methods rather than treat- ing them as distinct blocks.
Algorithmen im Feld der Geometrieverarbeitung benötigen in vielen Fällen die Lösung linearer Gleichungssysteme, die im Zusammenhang mit diskreten Laplace Operatoren stehen. Häufig stellt dies eine zentrale Operation dar, die die Laufzeit des Algorithmus maßgeblich mitbestimmt. Normalerweise werden dafür hoch optimierte Programmbibliotheken eingesetzt, die jedoch für sehr allgemeine lineare Systeme erstellt wurden. In dieser Arbeit schlage ich vor, effizientere Algorithmen zu konstruieren, indem die Struktur dieser Programmbibliotheken modifiziert und ausgenutzt wird. Der Fokus liegt hierbei auf der Cholesky Zerlegung, die im Kontext der Geometrieverarbeitung häufig Verwendung findet. Dabei interessiere ich mich besonders für Teile der Lösung linearer Gleichungssysteme, die zu einer lokalisierten Region auf dreidimension- alen Dreiecksnetzen gehören. Die zentrale Frage dabei lautet: Angenommen die Cholesky Zerlegung eines linearen Gleichungssystems, definiert auf dem gesamten Netz, ist gegeben. Wie kann man die Lösung an einer kleinen lokalisierten Menge von Knotenpunkten, möglicherweise unter neu gewählten Randbedingungen, effizient bestimmen? In dieser Arbeit zeige ich Wege auf, wie dies, ohne die Lösung an allen Knotenpunkten zu bestimmen oder die Zerlegung komplett neu zu berechnen, erreicht werden kann. Dazu ist es notwendig, die Funktionsweise von Methoden zur Cholesky Zerlegung dünnbesetzter Matrizen zu analysieren, um sie dann in geeigneter Weise zu modifizieren. Die Methoden werden anhand konkreter Anwendungsbeispiele analysiert. Im Idealfall kann diese Dissertation zukünftige Forschung im Bereich der Geometrieverarbeitung und verwandter Felder stimulieren, Algorithmen und numerische Methode gemeinsam zu entwickeln und sie nicht mehr als unabhängige Teile zu verstehen.
