Factor Once: Reusing Cholesky Factorizations on Sub-Meshes

摘要

A common operation in geometry processing is solving symmetric andpositive semi-definite systems on a subset of a mesh, with conditions for thevertices at the boundary of the region. This is commonly done by settingup the linear system for the sub-mesh, factorizing the system (potentiallyapplying preordering to improve sparseness of the factors), and then solvingby back-substitution. This approach suffers from a comparably high setupcost for each local operation. We propose to reuse factorizations definedon the full mesh to solve linear problems on sub-meshes. We show howan update on sparse matrices can be performed in a particularly efficientway to obtain the factorization of the operator on a sun-mesh significantlyoutperforming general factor updates and complete refactorization. Weanalyze the resulting speedup for a variety of situations and demonstratethat our method outperforms factorization of a new matrix by a factor of upto 10 while never being slower in our experiments.