6

对于当前的项目，我必须计算许多具有相同矩阵（非常稀疏）的向量的内积。向量与二维网格相关联，因此我将向量存储在一个三维数组中：

例如：

X是一个 dim 数组(I,J,N)。矩阵A是暗淡的(N,N)。现在的任务是计算A.dot(X[i,j])每个i,jin I,J。

对于 numpy 数组，这很容易实现

Y = X.dot(A.T)

现在我想存储A为稀疏矩阵，因为它是稀疏的，并且只包含非常有限数量的非零条目，这会导致很多不必要的乘法。不幸的是，上述解决方案不起作用，因为 numpy dot 不适用于稀疏矩阵。据我所知，scipy sparse 没有类似张量点的操作。

有人知道Y用稀疏矩阵计算上述数组的好方法A吗？

4

1 回答 1

3

显而易见的方法是在向量​​上运行一个循环并使用稀疏矩阵的.dot方法：

def naive_sps_x_dense_vecs(sps_mat, dense_vecs):
    rows, cols = sps_mat.shape
    I, J, _ = dense_vecs.shape
    out = np.empty((I, J, rows))
    for i in xrange(I):
        for j in xrange(J):
            out[i, j] = sps_mat.dot(dense_vecs[i, j])
    return out

但是您可以通过将 3d 数组重塑为 2d 并避免 Python 循环来加快速度：

def sps_x_dense_vecs(sps_mat, dense_vecs):
    rows, cols = sps_mat.shape
    vecs_shape = dense_vecs.shape
    dense_vecs = dense_vecs.reshape(-1, cols)
    out = sps_mat.dot(dense_vecs.T).T
    return out.reshape(vecs.shape[:-1] + (rows,))

问题是我们需要将稀疏矩阵作为第一个参数，这样我们才能调用它的.dot方法，这意味着返回是转置的，这反过来意味着在转置之后，最后的reshape会触发一个副本整个数组。因此，对于相当大的I和值J，结合不太大的 值N，后一种方法将比前一种方法快几倍，但对于其他参数组合，性能甚至可能相反：

n, i, j = 100, 500, 500
a = sps.rand(n, n, density=1/n, format='csc')
vecs = np.random.rand(i, j, n)

>>> np.allclose(naive_sps_x_dense_vecs(a, vecs), sps_x_dense_vecs(a, vecs))
True

n, i, j = 100, 500, 500
%timeit naive_sps_x_dense_vecs(a, vecs)
1 loops, best of 3: 3.85 s per loop
%timeit sps_x_dense_vecs(a, vecs)
1 loops, best of 3: 576 ms per 

n, i, j = 1000, 200, 200
%timeit naive_sps_x_dense_vecs(a, vecs)
1 loops, best of 3: 791 ms per loop
%timeit sps_x_dense_vecs(a, vecs)
1 loops, best of 3: 1.3 s per loop
于 2013-09-19T19:54:18.830 回答