Python稀疏矩阵乘法

Question

假设我有两个稠密矩阵U（10000x50）和V（50x10000），以及一个稀疏矩阵A（10000x1000）。中的每个元素都是1或0。我希望找到一个*（UV），注意到'*'是元素乘法。为了解决这个问题，Scipy/numpy将首先计算密集矩阵UV。但是紫外线是密集的和大的（10000x1000），所以它非常慢。在

因为我只需要a表示的几个UV元素，所以如果只计算必要的元素而不是计算所有元素然后使用a进行过滤，应该可以节省很多时间。有没有方法可以指导scipy执行此操作？在

顺便说一句，我用Matlab来解决这个问题，而Matlab足够聪明，可以找到我要做的事情，并且工作效率很高。在

更新： 我发现Matlab完全像scipy一样计算紫外线。我的scipy安装太慢了。。。在

Answer 1

这里有一个测试脚本和可能的加速。基本思想是使用A的非零坐标来选择U和{}的行和列，然后使用einsum来执行可能的点积的子集。在

import numpy as np
from scipy import sparse

#M,N,d = 10,5,.1
#M,N,d = 1000,50,.1
M,N,d = 5000,50,.01   # about the limit for my memory

A=sparse.rand(M,M,d)
A.data[:] = 1   # a sparse 0,1 array
U=(np.arange(M*N)/(M*N)).reshape(M,N)
V=(np.arange(M*N)/(M*N)).reshape(N,M)

A1=A.multiply(U.dot(V))   # the direct solution
A2=np.einsum('ij,ik,kj->ij',A.A,U,V)

print(np.allclose(A1,A2))

def foo(A,U,V):
    # use A to select elements of U and V
    A3=A.copy()
    U1=U[A.row,:]
    V1=V[:,A.col]
    A3.data[:]=np.einsum('ij,ji->i',U1,V1)
    return A3

A3 = foo(A,U,V)

print(np.allclose(A1,A3.A))

三种解决方案相匹配。{2>对于大数组，{cd5}比直接数组快。对于小尺寸，纯的einsum是有竞争力的，但是对于大的阵列则陷入困境。在

在foo中使用dot会计算出太多的乘积，ij,jk->ik而不是{}。在