python中的稀疏矩阵的矩阵乘方 [英] Matrix power for sparse matrix in python

问题描述

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

I am trying to find out a way to do a matrix power for a sparse matrix M: M^k = M*...*M k times where * is the matrix multiplication (numpy.dot), and not element-wise multiplication.

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

I know how to do it for a normal matrix:

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做到这一点:

How can I do it for sparse M:

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

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

Of course, I can do this by recursive multiplications, but I am wondering if there is a functionality like matrix_power for sparse matrices in scipy. Any help is much much appreciated. Thanks in advance.

推荐答案

**已针对csr_matrix实现.有__pow__方法.

** has been implemented for csr_matrix. There is a __pow__ method.

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

After handling some special cases this __pow__ does:

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

对于稀疏矩阵，*是矩阵乘积(对于ndarray，dot).因此它正在执行递归乘法.

For sparse matrix, * is the matrix product (dot for ndarray). So it is doing recursive multiplications.

如math所述，np.matrix还将**(__pow__)实现为矩阵幂.实际上，它最终调用了np.linalg.matrix_power.

As math noted, np.matrix also implements ** (__pow__) as matrix power. In fact it ends up calling np.linalg.matrix_power.

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

np.linalg.matrix_power(M, n) is written in Python, so you can easily see what it does.

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

对于较大的n，它将进行二进制分解以减少dot的总数.我认为这对于n=4:

For larger n, it does a binary decomposition to reduce the total number of dots. I assume that means for n=4:

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

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

The sparse version isn't as general. It can only handle positive integer powers.

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

You can't count on numpy functions operating on spare matrices. The ones that do work are the ones that pass the action on to the array's own method. e.g. np.sum(A) calls A.sum().

这篇关于python中的稀疏矩阵的矩阵乘方的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！