具有互换行和列的稀疏 cholesky 分解

Question

我正在使用 python 的 scikits.sparse.cholmod 来获得对称矩阵的 cholesky 分解。

我比较了 cholesky() 与 matlab 的 chol() 的结果。结果有一些行和列互换的差异。我正在尝试遍历因式分解以获得特征值，但这种差异似乎有问题。

这是我的代码：

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse import csc_matrix
from scikits.sparse.cholmod import cholesky

A = csr_matrix([[1,2,0,0], [0,0,3, 0], [4,0,5, 0], [0, 0, 1, 2]])
B = (A*A.T)
print "B: "
print B.todense()

for i in range(10):
    factor = cholesky(B.tocsc())
    l = factor.L()  #l is lower triangular
    B = (l.T*l)
    print l.todense()

第一次迭代的下三角矩阵为：

[[ 2.23606798  0.         0.          0.        ]
[ 0.          3.          0.          0.        ]
[ 0.          1.          2.          0.        ]
[ 1.78885438  5.          0.          3.57770876]]

而matlab的下三角矩阵为：

[2.2361        0         0         0
     0    3.0000         0         0
1.7889    5.0000    3.5777         0
     0    1.0000         0    2.0000]

matlab 结果是合理的，因为它产生了正确的特征值。我在 python 中选择稀疏矩阵类型做错了吗？

Answer 1

cholesky 算法使用的是填充减少算法。因此，它设置了一个置换矩阵 P。这样 LL'=PBP'.

您可以参考factor documentation了解更多信息。

如果你打印 P 你会得到：

>>> factor.P()
array([0, 1, 3, 2], dtype=int32)

这正是两个矩阵的区别。最后两行和两列的排列。

具有互换行和列的稀疏 cholesky 分解

sparse cholesky decomposition with interchanged rows and columns

python

sparse-matrix

matrix-factorization