用极稀疏矩阵相乘的最快方法是什么? [英] What is the fastest way to multiply with extremely sparse matrix?

问题描述

我的结构矩阵非常稀疏.我的矩阵每列只有一个非零条目.但是它巨大(10k * 1M)，并以以下形式给出(例如使用随机值)

I have an extremely sparse structured matrix. My matrix has exactly one non zero entry per column. But its huge(10k*1M) and given in following form(uisng random values for example)

rows = np.random.randint(0, 10000, 1000000)
values = np.random.randint(0,10,1000000)

其中，行为我们提供了每一列中非零条目的行号.我想要与S进行快速矩阵乘法，并且现在正在执行以下操作-我将此形式转换为稀疏矩阵(S)，然后将S.dot(X)与矩阵X(可以是稀疏或稠密)相乘.

where rows gives us the row number for nonzero entry in each column. I want fast matrix multiplication with S and I am doing following right now - I convert this form to a sparse matrix(S) and do S.dot(X) for multiplication with matrix X(which can be sparse or dense).

S=scipy.sparse.csr_matrix( (values, (rows, scipy.arange(1000000))), shape = (10000,1000000))

对于大小为1M * 2500的X和nnz(X)= 8M的X，创建S需要178毫秒，应用S则需要255毫秒.所以我的问题是，鉴于我所描述的S，做SX(X可能稀疏或密集)的最佳方法是什么.由于创建S本身非常耗时，所以我想到了一些特别的东西.我确实尝试过使用循环创建一些东西，但它甚至还没有结束.
简单的循环过程看起来像这样

For X of size 1M * 2500 and nnz(X)=8M this takes 178ms to create S and 255 ms to apply it. So my question is this what is the best way of doing SX (where X could be sparse or dense) given my S is as described. Since creating S is itself very time consuming I was thinking of something adhoc. I did try creating something using loops but its not even close.
Simple looping procedure looks something like this

SX = np.zeros((rows.size,X.shape[1])) for i in range(X.shape[0]): SX[rows[i],:]+=values[i]*X[i,:] return SX
我们可以提高效率吗?

SX = np.zeros((rows.size,X.shape[1])) for i in range(X.shape[0]): SX[rows[i],:]+=values[i]*X[i,:] return SX
Can we make this efficient?

任何建议都将不胜感激.谢谢

Any suggestions are greatly appreciated. Thanks

推荐答案

受此帖子启发

Inspired by this post Fastest way to sum over rows of sparse matrix, I have found the best way to do this is to write loops and port things to numba. Here is the

`

@njit
def sparse_mul(SX,row,col,data,values,row_map):
    N = len(data)
    for idx in range(N):
        SX[row_map[row[idx]],col[idx]]+=data[idx]*values[row[idx]]
    return SX
X_coo=X.tocoo()
s=row_map.max()+1
SX = np.zeros((s,X.shape[1]))
sparse_mul(SX,X_coo.row,X_coo.col,X_coo.data,values,row_map)`

这里的row_map是问题中的行.在X大小为(1M * 1K)，稀疏度为1％且s = 10K的情况下，其性能是从row_map形成稀疏矩阵并执行S.dot(A)的两倍.

Here row_map is the rows in the question. On X of size (1M* 1K), 1% sparsity and with s=10K this performs twice as good as forming sparse matrix from row_map and doing S.dot(A).

这篇关于用极稀疏矩阵相乘的最快方法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！