Python中稀疏矩阵的矩阵乘法

Question

我想把一个稀疏矩阵A和一个元素为0、-1或1的矩阵B相乘。为了让这个矩阵相乘的过程更简单，我可以忽略那些值为0的元素；如果元素是1，我就可以直接把这一列加上，而不需要乘；如果是-1，我就减去这一列。关于这个讨论可以在这里找到：

随机投影算法伪代码

现在我可以开始实现这个技巧，但我在想如果使用Numpy的乘法函数会不会更快。

有没有人知道他们是否为这种矩阵优化了乘法？或者你能建议一些方法来加快这个过程吗？因为我有一个300000x1000的矩阵。

Answer 1

你有没有看过 scipy.sparse 这个库？其实没必要自己重新发明轮子。稀疏矩阵是一个相对标准的概念。

（在这个例子中，我使用了一个 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.]]