Presentation

Technical Papers
:
Factor once: Reusing Cholesky factorizations on sub-meshes
Event Type
Technical Papers
Registration Categories
TimeWednesday, 5 December 20183:39pm - 4pm
DescriptionA common operation in geometry processing involves solving symmetric, positive definite systems on a subset of a mesh, with conditions for the vertices on the boundary of the region.
This is commonly done by setting up the linear system for the sub-mesh, factorizing the system (potentially applying preordering to improve sparseness of the factors), and then solving by back-substitution. This approach suffers from a comparably high setup cost for each local operation. We propose to reuse factorizations defined on the full mesh to solve linear problems on sub-meshes. We show how this update on sparse matrices can be performed in a particularly efficient way, significantly outperforming general factor updates. We analyze the resulting speed-up for a variety of situations and demonstrate that our method outperforms factorization of a new matrix by a factor of up to 10 while never beeing slower in our experiments.