Department of Chemistry, University of California, Berkeley, California 94720, United States, and Chemical Sciences Division, Lawrence Berkeley National Laboratory, Berkeley, California, United States.
J Chem Theory Comput. 2011 Feb 8;7(2):351-68. doi: 10.1021/ct100618s. Epub 2011 Jan 10.
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.
在这里，我们提出了一种高效的、非线性格式化算法，用于计算稀疏对称正定矩阵的 Cholesky 因子及其逆。该实现的关键特点是将任务分为代数部分和数值部分。算法的代数部分试图找到一种行和列的重新排序方式，这种方式至少可以保留一定程度的稀疏性，然后确定 Cholesky 因子及其相应逆的精确非零结构。它基于图论，不涉及任何类型的数值阈值处理。这种预处理随后允许非常有效地实现数值分解步骤。此外，这种方法甚至允许使用高度优化的密集线性代数内核，从而进一步提高性能。我们将展示一些稀疏代码的说明性计时，并将其与标准库实现以及使用阈值处理的最新稀疏实现进行比较。最后，我们将讨论如何处理半正定矩阵。
