12

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

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

稠密

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

疏

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

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

置换矩阵

根据讲义

存在许多用于选择好的置换矩阵 P 的启发式方法（我们没有介绍）。

我想知道其中一些方法是什么（C、C++ 甚至 Java 中的代码是理想的）。

4

1 回答 1

9

为最小填充矩阵分解找到矩阵的行和列的最佳排列的问题并非易事（如评论中所指出的那样）。因此，启发式算法在实践中被使用。

有一些库实现了启发式重新编号/排序策略，通常基于矩阵邻接图的图算法。一种尝试减少相应邻接矩阵的带宽。一种易于实现的算法是Cuthill-McKee 算法或最小度排序算法。更多关于这个问题的信息可以在Yousef Saad: Iterative Methods for Sparse Linear Systems (2003)一书中找到。

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

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

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

于 2015-04-18T10:42:03.320 回答