Locally Solving Linear Systems for Geometry Processing

Abstract

Geometry processing algorithms commonly need to solve linear systems involving discrete Laplacians. In many cases this constitutes a central building block of the algorithm and dominates runtime. Usually highly optimized libraries are employed 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 exploiting 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 factorizations 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 obtain 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 detailed understanding of sparse Cholesky factorizations and modifications of their implementation. The methods are analyzed and validated in concrete applications. Ideally this thesis will stimulates research in geometry processing and related fields to jointly develop algorithms and numerical methods rather than treating them as distinct blocks.