两个巨大的稠密矩阵 Hadamard-乘以一个稀疏矩阵的乘法

Question

我有两个密集矩阵 A 和 B，每个矩阵的大小都为 3e5x100。另一个稀疏二进制矩阵 C，大小为 3e5x3e5。我想找到以下数量：C ∘ (AB')，其中 ∘ 是 Hadamard 乘积（即元素明智），B' 是 B 的转置。显式计算 AB' 会要求疯狂的内存量（~500GB）。由于最终结果不需要整个 AB'，因此只计算乘法 A_iB_j' 就足够了，其中 C_ij != 0，其中 A_i 是列 i矩阵 A 和 C_ij 的元素是矩阵 C 位置 (i,j) 处的元素。建议的方法类似于以下算法：

result = numpy.initalize_sparse_matrix(shape = C.shape)
while True:
 (i,j) = C_ij.pop_nonzero_index() #prototype function returns the nonzero index and then points to the next nonzero index
 if (i,j) is empty:
   break
 result(i,j) = A_iB_j'

但是这个算法需要太多时间。有没有办法使用 LAPACK/BLAS 算法对其进行改进？我在 Python 中编码，所以我认为 numpy 可以更人性化地包装 LAPACK/BLAS。

Answer 1

您可以使用以下方法进行计算，假设 C 存储为 scipy.sparse 矩阵：

C = C.tocoo()
result_data = C.data * (A[C.row] * B[C.col]).sum(1)
result = sparse.coo_matrix((result_data, (row, col)), shape=C.shape)

这里我们表明结果与一些较小输入的朴素算法相匹配：

import numpy as np
from scipy import sparse

N = 300
M = 10

def make_C(N, nnz=1000):
  data = np.random.rand(nnz)
  row = np.random.randint(0, N, nnz)
  col = np.random.randint(0, N, nnz)
  return sparse.coo_matrix((data, (row, col)), shape=(N, N))


A = np.random.rand(N, M)
B = np.random.rand(N, M)
C = make_C(N)

def f_naive(C, A, B):
  return C.multiply(np.dot(A, B.T))

def f_efficient(C, A, B):
  C = C.tocoo()
  result_data = C.data * (A[C.row] * B[C.col]).sum(1)
  return sparse.coo_matrix((result_data, (C.row, C.col)), shape=C.shape)

np.allclose(
    f_naive(C, A, B).toarray(),
    f_efficient(C, A, B).toarray()
)
# True

在这里我们看到它适用于完整的输入大小：

N = 300000
M = 100

A = np.random.rand(N, M)
B = np.random.rand(N, M)
C = make_C(N)

out = f_efficient(C, A, B)

print(out.shape)
# (300000, 300000)

print(out.nnz)
# 1000

两个巨大的稠密矩阵 Hadamard-乘以一个稀疏矩阵的乘法

Multiplication of two huge dense matrices Hadamard-multiplied by a sparse matrix

python

numpy

matrix

sparse-matrix

lapack