python - python中稀疏矩阵的矩阵幂

Question

我正在尝试找出一种方法来为稀疏矩阵 M 计算矩阵幂:M^k = M*...*M k 次，其中 * 是矩阵乘法 (numpy.dot)，不是逐元素乘法。

我知道如何对普通矩阵执行此操作:

import numpy as np
import scipy as sp
N=100
k=3
M=(sp.sparse.spdiags(np.ones(N), 0, N, N)-sp.sparse.spdiags(np.ones(N), 2, N, N)).toarray()
np.matrix_power(M,k)

我如何为稀疏 M 做这件事:

M=(sp.sparse.spdiags(np.ones(N), 0, N, N)-sp.sparse.spdiags(np.ones(N), 2, N, N))

当然，我可以通过递归乘法来做到这一点，但我想知道 scipy 中是否有像 matrix_power 这样的稀疏矩阵的功能。非常感谢任何帮助。提前致谢。

Answer 1

**已为 csr_matrix 实现.有一个 __pow__方法。

在处理了一些特殊情况后这__pow__做:

            tmp = self.__pow__(other//2)
            if (other % 2):
                return self * tmp * tmp
            else:
                return tmp * tmp

对于稀疏矩阵，*是矩阵乘积(dot 对于 ndarray)。所以它在做递归乘法。

---

作为math注意到，np.matrix还实现了 ** ( __pow__ ) 作为矩阵幂。事实上它最终调用了 np.linalg.matrix_power .

np.linalg.matrix_power(M, n)是用 Python 编写的，因此您可以轻松查看它的作用。

对于 n<=3只是重复dot .

对于更大的 n , 它进行二进制分解以减少 dot 的总数秒。我认为这意味着 n=4 :

result = np.dot(M,M)
result = np.dot(result,result)

稀疏版本并不通用。它只能处理正整数幂。

你不能指望numpy在备用矩阵上运行的函数。那些起作用的是将操作传递给数组自己的方法的那些。例如np.sum(A)电话 A.sum() .