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

Question

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

pythonnumpymatrixsparse-matrixmatrix-multiplication

4

在Python中使用NumPy，假设我有两个矩阵：

1. S，一个稀疏的x*x矩阵。 2. M，一个密集的x*y矩阵。

现在我想要执行np.dot(M, M.T)，这将返回一个密集的x*x矩阵S_。

然而，我只关心S中非零的单元格，这意味着如果我执行S_ = S*S_，对于我的应用程序没有影响，因为我可以完全省略给定在S中的无关单元格。请记住，在矩阵乘法中

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

所以我只想为S[i,j]=True的i和j执行这个操作。

是否有numpy实现支持这样的操作，在C中运行，因此我不需要使用Python循环来实现它？

编辑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)) )

......但仍然很慢。有任何新的想法吗？

编辑2：jdehesa提供了一个很好的解决方案，但我希望节省更多内存。

解决方案如下：

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

接下来从 rows, cols 和 data 创建一个新的稀疏矩阵。

然而，运行以上代码时，scipy会建立一个（连续的）numpy数组，该数组的元素数量为第一个子矩阵的nnz加上第二个子矩阵的nnz，这可能会在我的情况下导致MemoryError。

为了更节省内存，我想要将每一行与其对应的'partner'列进行迭代相乘，然后求和并丢弃结果向量。使用简单的Python实现这一过程，基本上回到了极慢的版本。

是否有一种快速解决这个问题的方法？

- Radio Controlled

这些数组的大小是多少？S 的稀疏度是多少？一个小例子可能会有所帮助，只要确保我们在同一页面上。除非 S 非常稀疏，否则额外的选择工作可能会抵消任何计算时间的节省。 - hpaulj

问题在于，如果整个矩阵被计算出来，输出矩阵将会太大而无法存储在内存中。 - Radio Controlled

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- jdehesa · Accepted Answer

以下是使用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]))