python - 将大型稀疏矩阵与其转置相乘的最佳方法是什么？

Question

我目前想要将一个大的稀疏矩阵(~1M x 200k)与其转置相乘。结果矩阵的值将是 float 。

• 我尝试将矩阵加载到 scipy 的稀疏矩阵中，并将第一个矩阵的每一行与第二个矩阵相乘。乘法需要大约 2 小时才能完成。

实现这种乘法的有效方法是什么？因为我在计算中看到了一个模式。

• 矩阵大而稀疏。
• 矩阵与其转置相乘。因此，生成的矩阵将是对称的。

我想知道哪些库可以更快地实现计算。它可以是 Python、R、C、C++ 或任何其他语言。

Answer 1

我想您的主要需求是节省内存。首先，当您将矩阵与其转置相乘时，转置不需要任何内存:它的所有单元格都可以通过第一个矩阵 (tA[i,j] = A[j,i]) 直接访问。几乎节省了 1/3 的内存。

我可以看出计算时间也不能忽略。由于生成的矩阵是对称的，您可以只计算一半并直接存储另一半。节省了近一半的计算时间。

如果您确定您的初始矩阵确实是稀疏的，并且希望生成的矩阵也是稀疏的，您可以直接将结果存储在 scipy 稀疏矩阵中，COO 格式:只有三个列表来存储非空值。

但是......我不知道有任何库可以做到这一点，你必须用你喜欢的语言(可能是 python，因为你说的是​​ scipy)自己编写代码。

Python 代码示例(矩阵 = A[M][N])

I = []
J = []
V = []
for i in range(M):
    for j in range(i:M) :
        X = 0.0
        for k in range(N):
            X += A[i ][k] * A[k][j]
        if X != 0.0 # or abs (X) > epsilon if floating point accuracy is a concern ... 
            I.append (i )
            J.append(j)
            V.append(X)
            I.append (j )
            J.append(i)
            V.append(X)

而 I、J、V 是 scipy COO 稀疏矩阵所需要的:

RESULT = sparse.coo_matrix((V,(I,J)),shape=(N, N))