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

Question

我对大型稀疏矩阵的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中的代码都是理想的).

Answer 1

找到矩阵的行和列的最佳排列以进行最小填充矩阵分解的问题不是一个简单的trask(如评论中所指出的).因此,启发式算法用于实践.

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

许多库实现启发式算法,如

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

其中一些库也提供稀疏的Cholesky分解方法,可以直接使用.