algorithm - 使用置换矩阵对稀疏矩阵进行 Cholesky 分解

Question

我对大型稀疏矩阵的 Cholesky 分解很感兴趣。我遇到的问题是 Cholesky 因子不一定是稀疏的(就像两个稀疏矩阵的乘积不一定是稀疏的一样)。

例如，对于仅沿第一行、第一列和对角线具有非零值的矩阵，Cholesky 因子具有 100% 填充(下三角形和上三角形是 100% 密集的)。在image灰色下方为非零，白色为零。

我知道的一种解决方案是找到置换P 矩阵并对P^TAP 进行Cholesky 分解。例如，对于相同的矩阵，通过应用将第一行移动到最后一行并将第一列移动到最后一列的置换矩阵，Cholesky 因子是稀疏的。

我的问题是一般情况下如何确定 P？

要从更真实的矩阵中了解 A 和 P^TAP 的 Cholesky 分解的差异，请参见下图.我从 http://www.seas.ucla.edu/~vandenbe/103/lectures/chol.pdf 中拍摄了所有这些图像

根据lecture notes

many heuristic methods (that we don’t cover) exist for selecting good permutation matrices P.

我想知道其中一些方法是什么(用 C、C++ 甚至 Java 编写的代码是理想的)。

Answer 1

为最小填充矩阵分解找到矩阵的行和列的最佳排列的问题不是一个微不足道的任务(正如评论中指出的那样)。因此，启发式算法在实践中得到了应用。

有一些库实现启发式重新编号/排序策略，通常基于矩阵的邻接图的图算法。一种尝试减少相应邻接矩阵的带宽。一个易于实现的算法是 Cuthill-McKee Algorithm或 Minimum-Degree Ordering算法。有关此问题的更多信息，请参阅本书 Yousef Saad: Iterative Methods for Sparse Linear Systems (2003) , 在许多其他人身上。

许多库实现了启发式算法，例如

• Suitesparse用于大型稀疏线性系统的直接求解器的库集合。在库 AMD、CAMD、COLAMD 和 CCOLAMD 中实现的排序方法
• (Par-)Metis用于图分区的库，但也提供矩阵重排序算法
• > Boost.Graph直接处理邻接图并提供一些排序算法，如提到的 Cuthill-McKee 和最小度排序
• (PT-)Scotch用于图分区和稀疏矩阵重排序

其中一些库还提供稀疏 Cholesky 分解方法，可以直接使用。