哪个是将大型稀疏矩阵与其转置相乘的最佳方法？

Question

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

• 我尝试在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))