Python中稀疏矩阵的矩阵乘法

Question

我想将稀疏矩阵a与矩阵B相乘，矩阵B的元素为0、-1或1。为了减少矩阵乘法的复杂性，我可以忽略为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.]]