Numpy：智能矩阵乘法到稀疏结果矩阵

Question

在 python 和 numpy 中，假设我有两个矩阵：

S，稀疏x*x矩阵
M，密集的x*y矩阵

现在我想做 np.dot(M, M.T) 这将 return 一个密集的 x*x 矩阵 S_.

但是，我只关心 S 中非零的单元格，这意味着如果我这样做了，它不会对我的应用程序产生影响

S_ = S*S_

显然，这会浪费操作，因为我想将 S 中给出的不相关单元格一起排除。请记住，在矩阵乘法

S_[i,j] = np.sum(M[i,:]*M[:,j])

所以我只想对 i,j 执行此操作，这样 S[i,j]=True.

C 中运行的 numpy 实现是否以某种方式支持此功能，以便我不需要使用 python 循环来实现它？

EDIT 1 [已解决]: 我还有这个问题，实际上M现在也稀疏了。

现在，给定 S 的行数和列数，我是这样实现的：

data = np.array([ M[rows[i],:].dot(M[cols[i],:]).data[0] for i in xrange(len(rows)) ])
S_   = csr( (data, (rows,cols)) )

...但它仍然很慢。 有什么新想法吗？

EDIT 2: jdehesa 给出了一个很好的解决方案，但我想节省更多内存。

解决方案是执行以下操作：

data = M[rows,:].multiply(M[cols,:]).sum(axis=1)

然后从 rows、cols 和 data.

构建一个新的稀疏矩阵

但是，当运行上面的行时，scipy 构建一个（连续的）numpy 数组，其元素与第一个子矩阵的 nnz 加上 nnz 一样多第二个子矩阵，在我的例子中可以导致 MemoryError。

为了节省更多内存，我想将每一行与其各自的 'partner' 列迭代相乘，然后求和并丢弃结果向量。使用简单的python来实现，基本上我又回到了极慢的版本。

有没有快速解决这个问题的方法？

Answer 1

这里是你如何使用 NumPy/SciPy 来做到这一点，对于密集和稀疏 M 矩阵：

import numpy as np
import scipy.sparse as sp

# Coordinates where S is True
S = np.array([[0, 1],
              [3, 6],
              [3, 4],
              [9, 1],
              [4, 7]])

# Dense M matrix
# Random big matrix
M = np.random.random(size=(1000, 2000))
# Take relevant rows and compute values
values = np.sum(M[S[:, 0]] * M[S[:, 1]], axis=1)
# Make result matrix from values
result = np.zeros((len(M), len(M)), dtype=values.dtype)
result[S[:, 0], S[:, 1]] = values

# Sparse M matrix
# Construct sparse M as COO matrix or any other way
M = sp.coo_matrix(([10, 20, 30, 40, 50],  # Data
                   ([0, 1, 3, 4, 6],      # Rows
                    [4, 4, 5, 5, 8])),    # Columns
                  shape=(1000, 2000))
# Convert to CSR for fast row slicing
M_csr = M.tocsr()
# Take relevant rows and compute values
values = M_csr[S[:, 0]].multiply(M_csr[S[:, 1]]).sum(axis=1)
values = np.squeeze(np.asarray(values))
# Construct COO sparse matrix from values
result = sp.coo_matrix((values, (S[:, 0], S[:, 1])), shape=(M.shape[0], M.shape[0]))

Numpy：智能矩阵乘法到稀疏结果矩阵

Numpy: smart matrix multiplication to sparse result matrix

python

numpy

matrix

sparse-matrix

matrix-multiplication