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.