MeshFEM: A Block-accelerated Solver for Nonlinear Finite Elements
Open Access
- 3 July 2026
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Graphics
- Vol. 45 (4) , 1-22
Abstract
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.Keywords
Funding Information
- United States-Israel Binational Science Foundation (2020154)
- National Science Foundation (2443973)
- National Science Foundation (2411351)
This publication has 59 references indexed in Scilit:
- A flexible sparse matrix data format and parallel algorithms for the assembly of finite element matrices on shared memory systemsParallel Computing, 2023
- Accelerating sparse Cholesky factorization on GPUsParallel Computing, 2016
- Nonlinear Solid Mechanics for Finite Element Analysis: Statics2016
- Solving unsymmetric sparse systems of linear equations with PARDISOFuture Generation Computer Systems, 2004
- One-to-one piecewise linear mappings over triangulationsMathematics of Computation, 2002
- PARDISO: a high-performance serial and parallel sparse linear solver in semiconductor device simulationFuture Generation Computer Systems, 2001
- REFINED CONSISTENT FORMULATION OF A CURVED TRIANGULAR FINITE ROTATION SHELL ELEMENTInternational Journal for Numerical Methods in Engineering, 1996
- The incomplete Cholesky—conjugate gradient method for the iterative solution of systems of linear equationsJournal of Computational Physics, 1978
- A note on mass lumping and related processes in the finite element methodEarthquake Engineering & Structural Dynamics, 1976
- The Bose-Nelson Sorting Problem††The preparation of this report has been supported in part by the National Science Foundation, and in part by the Office of Naval Research.1973