python - 如何从更大的稀疏矩阵的 block 总和中有效地创建新矩阵

Question

我有一个大的 scipy 稀疏对称矩阵，我需要通过对 block 求和来压缩它来制作一个新的更小的矩阵。

例如，对于一个 4x4 稀疏矩阵 A，我想创建一个 2x2 矩阵 B，其中 B[i,j] = sum(A[i:i+2,j:j+2])。

目前，我只是逐 block 重新创建压缩矩阵，但这很慢。关于如何优化这个的任何想法？

更新:这是一个示例代码，它工作正常，但对于我想在 10.000x10.000 中压缩的 50.000x50.000 的稀疏矩阵来说速度很慢:

>>> A = (rand(4,4)<0.3)*rand(4,4)
>>> A = scipy.sparse.lil_matrix(A + A.T) # make the matrix symmetric

>>> B = scipy.sparse.lil_matrix((2,2))
>>> for i in range(B.shape[0]):
...     for j in range(B.shape[0]):
...         B[i,j] = A[i:i+2,j:j+2].sum()

Answer 1

首先，您总结的 lil 矩阵可能真的很糟糕，我会尝试 COO 或者 CSR/CSS (我不知道哪个更好，但是 lil 对于许多这些操作来说可能天生就慢，即使切片也可能慢得多，尽管我没有测试)。 (除非您知道例如 dia 非常适合)

基于 COO 我可以想象做一些欺骗。因为 COO 有 row 和 col 数组来给出准确的位置:

matrix = A.tocoo()

new_row = matrix.row // 5
new_col = matrix.col // 5
bin = (matrix.shape[0] // 5) * new_col + new_row
# Now do a little dance because this is sparse,
# and most of the possible bin should not be in new_row/new_col
# also need to group the bins:
unique, bin = np.unique(bin, return_inverse=True)
sum = np.bincount(bin, weights=matrix.data)
new_col = unique // (matrix.shape[0] // 5)
new_row = unique - new_col * (matrix.shape[0] // 5)

result = scipy.sparse.coo_matrix((sum, (new_row, new_col)))

(我不保证我没有在某处混淆行和列，这只适用于方阵...)