使用置换矩阵的稀疏矩阵的 Cholesky 分解 [英] Cholesky decomposition of sparse matrices using permutation matrices

问题描述

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

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

根据讲义

<块引用>

存在许多启发式方法(我们没有涵盖)用于选择好的置换矩阵 P.

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

解决方案

为最小填充矩阵分解找到矩阵的行和列的最佳排列的问题不是一个微不足道的问题(如在评论).因此，启发式算法被用于实践.

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

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

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

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

I am interested in the Cholesky decomposition of large sparse matrices. The problem I'm having is that the Cholesky factors are not necessarily sparse (just like the product of two sparse matrices is not necessarily sparse).

For example for a matrix with non-zeros only along the first row, first column, and diagonal the Cholesky factors have 100% fill-in (the lower and upper triangles are 100% dense). In the image below the gray is non zero and the white is zero.

One solution I'm aware is to find a permutation P matrix and do the Cholesky decomposition of P^TAP. For example with the same matrix by applying a permutation matrix which moves the first row to the last row and the first column to the last column the Cholesky factors are sparse.

My question is how to determine P in general?

To get an idea of the difference of the Cholesky decomposition of A and P^TAP from a more realistic matrix see the image below. I took all these images from http://www.seas.ucla.edu/~vandenbe/103/lectures/chol.pdf

According to the lecture notes

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

I would like to know what some of these methods are (code in C, C++, or even Java would be ideal).

解决方案

The problem of finding an optimal permutation of rows and columns of a matrix for a minimum fill-in matrix-factorization is not a trivial trask (as pointed out in the comments). Thus, heuristic algorithms are used in praxis.

There are some libraries that implement heuristic renumbering/ordering-strategies, often based on graph-algorithms for the adjacency-graph of your matrix. One tries to reduce the bandwidth of the corresponding adjacency-matrix. An easy to implement algroithms is the Cuthill-McKee Algorithm or the Minimum-Degree Ordering algorithm. More about this problem can be found in the Book Yousef Saad: Iterative Methods for Sparse Linear Systems (2003), upon many others.

Many libraries implement heuristic algorithms, like

• Suitesparse A collection of libraries for direct solvers for largse sparse linear systems. Ordering methods implemented in the libraries AMD, CAMD, COLAMD, and CCOLAMD
• (Par-)Metis A library for Graph-partitioning, but provides Matrix reordering algorithms as well
• Boost.Graph Working on the adjacency graph directly and provides some ordering algorithms, like the mentioned Cuthill-McKee, and Minimum-Degree Ordering
• (PT-)Scotch for Graph-partitioning and sparse-matrix reordering

Some of these libraries provide also sparse Cholesky factorization methods and can be used directly.

这篇关于使用置换矩阵的稀疏矩阵的 Cholesky 分解的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！