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

对于 numpy 矩阵，您也可以使用 ** 表示法代替 matrix_power :

a=np.matrix([[1,2],[2,1]])
a**3

输出：

matrix([[13, 14],
        [14, 13]])

用 scipy 稀疏矩阵试试。

Answer 2

** 已针对 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().

python 中稀疏矩阵的矩阵幂

Matrix power for sparse matrix in python

python

numpy

scipy

linear-algebra

sparse-matrix