Adaptive Algebraic Reuse of Reordering in Cholesky Factorizations with Dynamic Sparsity Patterns
Open Access
- 27 July 2025
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Graphics
- Vol. 44 (4) , 1-17
Abstract
We introduce Parth, a fill-reducing ordering method for sparse Cholesky solvers with dynamic sparsity patterns (e.g., in physics simulations with contact or geometry processing with local remeshing). Parth facilitates the selective reuse of fill-reducing orderings when sparsity patterns exhibit temporal coherence, avoiding full symbolic analysis by localizing the effect of dynamic sparsity changes on the ordering vector. We evaluated Parth on over 175,000 linear systems collected from both physics simulations and geometry processing applications, and show that for some of the most challenging physics simulations, it achieves up to 14x reordering runtime speedup, resulting in a 2x speedup in Cholesky solve time—even on top of well-optimized solvers such as Apple Accelerate and Intel MKL.Keywords
All Related Versions
This publication has 21 references indexed in Scilit:
- HDagg: Hybrid Aggregation of Loop-carried Dependence Iterations in Sparse Matrix Computations2022
- ParSy: Inspection and Transformation of Sparse Matrix Computations for Parallelism2018
- Accelerating sparse Cholesky factorization on GPUsParallel Computing, 2016
- A survey of direct methods for sparse linear systemsActa Numerica, 2016
- Algorithm 887ACM Transactions on Mathematical Software, 2008
- Row Modifications of a Sparse Cholesky FactorizationSIAM Journal on Matrix Analysis and Applications, 2005
- Algorithm 837ACM Transactions on Mathematical Software, 2004
- A remeshing approach to multiresolution modeling2004
- Computing the Minimum Fill-In is NP-CompleteSIAM Journal on Algebraic Discrete Methods, 1981
- Validity of the single processor approach to achieving large scale computing capabilities1967