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

问题描述

我感兴趣的大型稀疏矩阵的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).

例如与非零点仅沿着第一行，第一列，和对角线乔列斯基因子的矩阵有100％的填充式（下和上三角形是100％密实）。在下面的灰色图像是非零和白色是零。

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.

一个解决方案，我知道是要找到一个置换的 P 的基质和做的Cholesky分解的 P ^T AP 的。例如具有相同的基质通过将置换矩阵而移动的第一行到最后一行和第一列到最后一列的乔列斯基因素是稀疏

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.

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

My question is how to determine P in general?

要获取的 A 的的Cholesky分解的不同的想法和 P ^T AP 的距离更逼真的矩阵看下面的图片。我把所有的这些图片来自 HTTP：//www.seas.ucla。埃杜/〜vandenbe / 103 /讲座/ chol.pdf

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

按照讲义

许多启发式方法（即不包括），选择好存在   置换矩阵P中。

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

我想知道其中的一些方法（code在C，C ++甚至Java将是理想的）。

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.

有实现启发式重新编号/订货战略，往往是基于图的算法为邻接图的矩阵的一些库。人们试图降低对应的邻接矩阵的带宽。一个易于实现algroithms是 Cuthill - 麦基算法或<一HREF =htt​​p://en.wikipedia.org/wiki/Minimum_degree_algorithm相对=nofollow>最低-度排序算法。更多关于这个问题可以在书萨阿德优素福中找到：迭代方法稀疏线性系统（2003），在其他许多人。

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 直接求解器largse稀疏线性系统库的集合。订购的图书馆AMD，CAMD，COLAMD和CCOLAMD实现的方法
• （杆）梅蒂斯一个用于图形分区图书馆，但提供矩阵重排序算法，以及
• Boost.Graph 对邻接图直接工作并提供了一​​些排序算法，如提及Cuthill - 麦基和最小-度排序
• （PT-）苏格兰以图分区和稀疏矩阵重新排序

• 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

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

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

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