Adaptive Algebraic Reuse of Reordering in Cholesky Factorization with Dynamic Sparsity Pattern

Behrooz Zarebavani, Danny M. Kaufman, David I. W. Levin, Maryam Mehri DehnaviarXiv 2025 · arXiv · OpenReview

Abstract

Cholesky linear solvers are a critical bottleneck in challenging applications within computer graphics and scientific computing. These applications include but are not limited to elastodynamic barrier methods such as Incremental Potential Contact (IPC), and geometric operations such as remeshing and morphology. In these contexts, the sparsity patterns of the linear systems frequently change across successive calls to the Cholesky solver, necessitating repeated symbolic analyses that dominate the overall solver runtime. To address this bottleneck, we evaluate our method on over 150,000 linear systems generated from diverse nonlinear problems with dynamic sparsity changes in Incremental Potential Contact (IPC) and patch remeshing on a wide range of triangular meshes of various sizes. Our analysis using three leading sparse Cholesky libraries, Intel MKL Pardiso, SuiteSparse CHOLMOD, and Apple Accelerate, reveals that the primary performance constraint lies in the symbolic re-ordering phase of the solver. Recognizing this, we introduce Parth, an innovative re-ordering method designed to update ordering vectors only where local connectivity changes occur adaptively. Parth employs a novel hierarchical graph decomposition algorithm to break down the dual graph of the input matrix into fine-grained subgraphs, facilitating the selective reuse of fill-reducing orderings when sparsity patterns exhibit temporal coherence. Our extensive evaluation demonstrates that Parth achieves up to a 255x and 13x speedup in fill-reducing ordering for our IPC and remeshing benchmark and a 6.85x and 10.7x acceleration in symbolic analysis. These enhancements translate to up to 2.95x and 5.89x reduction in overall solver runtime. Additionally, Parth's integration requires only three lines of code, resulting in significant computational savings without the requirement of changes to the computational stack.

Introduction: The Reordering Bottleneck

Sparse Cholesky factorization is a fundamental tool in scientific computing, particularly for solving the large linear systems ($Ax = b$) that underpin physics-based animation and geometry processing. Traditionally, this process is divided into two distinct phases: symbolic analysis, which determines the matrix's structure to minimize fill-in, and numerical computation, where the actual arithmetic occurs.

In static scenarios, symbolic analysis is a one-time cost. However, modern graphics applications—such as character skinning with complex contact or real-time mesh refinement—feature "dynamic sparsity patterns" where the non-zero entries of the matrix change at every step. In these cases, the symbolic phase becomes a massive bottleneck, often consuming over 80% of the total solver runtime. Parth addresses this by localizing updates to the ordering vector rather than recalculating it from scratch.

The Parth Framework

Parth replaces the standard fill-reducing ordering module in existing solvers with a framework designed for adaptive algebraic reuse. It is built on three core components:

  1. Hierarchical Graph Decomposition (HGD): Instead of viewing the matrix as a single monolithic graph, Parth uses nested dissection to decompose it into a binary tree of sub-graphs and separators. This maps local matrix changes to specific branches of the hierarchy.
  2. Synchronizer: When the matrix structure changes (e.g., a new contact point in a simulation), the Synchronizer identifies the specific sub-graphs affected. It marks these regions as "dirty" while preserving the rest of the hierarchy.
  3. Assembler: This module reuses ordering vectors from "clean" sub-graphs and only recomputes permutations for the dirty regions, stitching them back into a high-quality global ordering vector.
Visualization of local remeshing on a head model, showing the localized 'dirty' region (yellow) where sparsity patterns change and require recomputation.

Key Insights and Evaluation

Parth exploits temporal coherence in sparsity. Even in chaotic simulations, changes are usually local—a few new triangles or a small contact patch. By confining computation to these regions, Parth avoids redundant work without requiring the user to manually specify where changes occur.

The method was evaluated using two massive benchmarks:

  • IPC (Incremental Potential Contact): Over 175,000 systems from large-deformation simulations with frequent self-collisions.
  • Remeshing: Solving the Laplace–Beltrami operator on triangle meshes while performing local remeshing, which alters both matrix values and dimensions.

Performance Results

Parth demonstrates that the real bottleneck in dynamic systems is the logic of reordering, not the numerical math. By integrating Parth into industry-standard libraries like Intel MKL and Apple Accelerate with just three lines of code, significant speedups were achieved.

Overview of the IPC and Remeshing benchmarks. The method achieves significant speedups in symbolic analysis and overall Cholesky solve times across diverse scenarios.

Key performance highlights include:

  • Reordering Speedup: Up to 14x speedup in the reordering step compared to standard methods (and up to 255x in specific IPC sub-tasks).
  • Total Solve Speedup: A 2x overall boost in total Cholesky solve time for complex physics simulations, reaching up to 5.89x in remeshing contexts.
  • Efficiency: In remeshing tests affecting only 2% of a mesh, Parth reused 92% of the previous ordering, resulting in a 5.5x faster solver.

Limitations and Future Work

Parth relies on the locality of changes. If a simulation involves widespread structural changes—such as an object exploding—the benefits of reuse diminish. Future research may focus on "adaptive numerical acceleration" to complement Parth's symbolic speedups, further reducing the cost of the numerical factorization phase.

Summary updated

Abstract

Cholesky linear solvers are a critical bottleneck in challenging applications within computer graphics and scientific computing. These applications include but are not limited to elastodynamic barrier methods such as Incremental Potential Contact (IPC), and geometric operations such as remeshing and morphology. In these contexts, the sparsity patterns of the linear systems frequently change across successive calls to the Cholesky solver, necessitating repeated symbolic analyses that dominate the overall solver runtime. To address this bottleneck, we evaluate our method on over 150,000 linear systems generated from diverse nonlinear problems with dynamic sparsity changes in Incremental Potential Contact (IPC) and patch remeshing on a wide range of triangular meshes of various sizes. Our analysis using three leading sparse Cholesky libraries, Intel MKL Pardiso, SuiteSparse CHOLMOD, and Apple Accelerate, reveals that the primary performance constraint lies in the symbolic re-ordering phase of the solver. Recognizing this, we introduce Parth, an innovative re-ordering method designed to update ordering vectors only where local connectivity changes occur adaptively. Parth employs a novel hierarchical graph decomposition algorithm to break down the dual graph of the input matrix into fine-grained subgraphs, facilitating the selective reuse of fill-reducing orderings when sparsity patterns exhibit temporal coherence. Our extensive evaluation demonstrates that Parth achieves up to a 255x and 13x speedup in fill-reducing ordering for our IPC and remeshing benchmark and a 6.85x and 10.7x acceleration in symbolic analysis. These enhancements translate to up to 2.95x and 5.89x reduction in overall solver runtime. Additionally, Parth's integration requires only three lines of code, resulting in significant computational savings without the requirement of changes to the computational stack.
BibTeX
@misc{zarebavani2025adaptive,
  author = {Behrooz Zarebavani and Danny M. Kaufman and David I. W. Levin and Maryam Mehri Dehnavi},
  title = {{Adaptive Algebraic Reuse of Reordering in Cholesky Factorization with Dynamic Sparsity Pattern}},
  year = {2025},
  eprint = {2501.04011},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2501.04011},
}

Loading related content...

Figure