标题： Cholesky分解中具有动态稀疏模式的自适应代数重用重新排序 显示英文标题

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

摘要： Cholesky线性求解器在计算机图形学和科学计算中的挑战性应用中是一个关键的瓶颈。 这些应用包括但不限于弹性动力学屏障方法，如增量势接触（IPC），以及几何操作，如重网格化和形态学。 在这些情况下，线性系统的稀疏模式在连续调用Cholesky求解器时经常发生变化，需要重复的符号分析，这主导了整体求解器运行时间。 为了解决这个瓶颈，我们在来自增量势接触（IPC）和各种大小的三角形网格上的补丁重网格化中具有动态稀疏变化的多样化非线性问题生成的超过150,000个线性系统上评估了我们的方法。 我们使用三个领先的稀疏Cholesky库，Intel MKL Pardiso、SuiteSparse CHOLMOD和Apple Accelerate进行分析，结果表明主要性能限制在于求解器的符号重新排序阶段。 认识到这一点，我们引入了Parth，一种创新的重新排序方法，旨在自适应地仅在局部连通性发生变化的地方更新排序向量。 Parth采用了一种新颖的分层图分解算法，将输入矩阵的对偶图分解成细粒度的子图，当稀疏模式表现出时间一致性时，促进填充减少排序的选择性重用。 我们的广泛评估表明，Parth在我们的IPC和重网格化基准测试中实现了填充减少排序高达255倍和13倍的速度提升，在符号分析中实现了6.85倍和10.7倍的加速。 这些改进转化为整体求解器运行时间高达2.95倍和5.89倍的减少。 此外，Parth的集成只需三行代码，从而在不需要更改计算堆栈的情况下实现显著的计算节省。 显示英文摘要

摘要： 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.