Python 中稀疏矩阵的矩阵乘法

Question

我想将稀疏矩阵 A 与以 0、-1 或 1 作为元素的矩阵 B 相乘。为了降低矩阵乘法的复杂性，如果项为 0，我可以忽略它们，或者如果项为 1 或 subs，则继续添加列而不进行乘法。如果是-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.]]