MeshFEM: A Block-accelerated Solver for Nonlinear Finite Elements

We introduce a high-performance framework for solving nonconvex optimization problems arising in simulation and geometry processing applications. Our framework especially benefits high-dimensional problems whose unknowns are spatial coordinates in ℝ d and whose objectives are expressed as a sum of element energies over small stencils. The Hessians of these problems have a block-sparse structure, where the nonzero entries are grouped into dense d × d blocks. Many works have exploited this structure to speed up the Hessian-vector products and nodal smoothers of iterative solvers. In contrast, accelerating direct sparse linear solvers, preferred for applications requiring high accuracy on unstructured grids, has been less explored. Our framework leverages block structure to accelerate all phases of a Newton-type minimization algorithm, from sparsity pattern construction to system assembly, matrix factorization, and solves. A fundamental piece of the framework is BlockCatamari, our highly tuned, block-accelerated multifrontal sparse Cholesky code that achieves significantly faster factorizations than existing direct solvers on shared-memory systems. We combine this solver with our fast parallel Hessian assembly routine, heuristics for conditionally enabling per-element Hessian projections, and strategies for minimizing symbolic factorization re-computations. We show that this leads to dramatic speedups on a large suite of benchmark problems involving injective surface parametrization and elasticity simulation with contact, and we further demonstrate the ease with which new energies can be defined at the different levels of abstraction offered by our framework.