Python中稀疏矩阵的矩阵乘法

Question

我想将稀疏矩阵A与矩阵B相乘,矩阵B具有0,-1或1作为元素.为了降低矩阵乘法的复杂性,我可以忽略它们为0的项目,或者如果项目为1或者sub则继续添加没有乘法的列.如果它是-1.关于这个的讨论在这里:

随机投影算法伪码

现在我可以继续实现这个技巧,但我想知道我是否使用Numpy的乘法函数它会更快.

有谁知道他们是否优化了这种矩阵的矩阵乘法？或者你可以建议一些东西来加快这个过程,因为我有一个矩阵300000x1000.

Answer 1

你看过了scipy.sparse吗？这里重新发明轮子是没有意义的.稀疏的matricies是一个相当标准的东西.

(在这个例子中,我使用300000x4矩阵在乘法后更容易打印.但300000x1000矩阵不应该是任何问题.假设你有大部分0元素,这将比乘以两个密集阵列快得多.)

import scipy.sparse
import numpy as np

# Make the result reproducible...
np.random.seed(1977)

def generate_random_sparse_array(nrows, ncols, numdense):
    """Generate a random sparse array with -1 or 1 in the non-zero portions"""
    i = np.random.randint(0, nrows-1, numdense)
    j = np.random.randint(0, ncols-1, numdense)
    data = np.random.random(numdense)
    data[data <= 0.5] = -1
    data[data > 0.5] = 1
    ij = np.vstack((i,j))
    return scipy.sparse.coo_matrix((data, ij), shape=(nrows, ncols))

A = generate_random_sparse_array(4, 300000, 1000)
B = generate_random_sparse_array(300000, 5, 1000)

C = A * B

print C.todense()

这会产生:

[[ 0.  1.  0.  0.  0.]
 [ 0.  2. -1.  0.  0.]
 [ 1. -1.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.]]