Fast Sparse Cholesky Decomposition and Inversion using Nested Dissection Matrix Reordering.
Fast Sparse Cholesky Decomposition and Inversion using Nested Dissection Matrix Reordering.
复制标题
使用嵌套剖析矩阵重新排序的快速稀疏 Cholesky 分解和反演。
DOI：
10.1021/ct100618s
复制
发表时间：
2011
影响因子：
5.5
通讯作者：
M. Head‐Gordon
中科院分区：
文献类型：
--
作者：
Kai Brandhorst;M. Head‐Gordon
在这里，我们提出了一个有效的，但非线性缩放，稀疏对称正定矩阵及其逆的Cholesky因子的计算算法。该实现的关键特征是将任务分离成代数和数值部分。该算法的代数部分试图找到一个重新排序的行和列，保留至少一定程度的稀疏性，然后确定精确的非零结构的乔莱斯基因子及其相应的逆。它基于图论，不涉及任何类型的数值阈值。然后，这种预处理允许非常有效地实现数值因式分解步骤。此外，这种方法甚至允许使用高度优化的密集线性代数内核，这导致另一个性能提升。我们将展示我们的稀疏代码的一些说明性时间，并将其与标准库实现和最近使用阈值的稀疏实现进行比较。最后，我们对如何处理半正定矩阵作了一些评论。
Here we present an efficient, yet nonlinear scaling, algorithm for the computation of Cholesky factors of sparse symmetric positive definite matrices and their inverses. The key feature of this implementation is the separation of the task into an algebraic and a numeric part. The algebraic part of the algorithm attempts to find a reordering of the rows and columns which preserves at least some degree of sparsity and afterward determines the exact nonzero structure of both the Cholesky factor and its corresponding inverse. It is based on graph theory and does not involve any kind of numerical thresholding. This preprocessing then allows for a very efficient implementation of the numerical factorization step. Furthermore this approach even allows use of highly optimized dense linear algebra kernels which leads to yet another performance boost. We will show some illustrative timings of our sparse code and compare it to the standard library implementation and a recent sparse implementation using thresholding. We conclude with some comments on how to deal with positive semidefinite matrices.