稀疏矩阵-矩阵乘法

Question

如何计算稀疏矩阵积？我知道“经典”/数学方法，但它似乎相当低效。还能改进吗？

我考虑将第一个矩阵存储在CSR表单中，第二个矩阵存储在CSC表单中，所以由于行和列向量是排序的，所以我不需要搜索我需要的特定行/列，但我想这没有多大帮助。

Answer 1

声明(i)你真的不想实现你自己的稀疏矩阵包，(ii)如果你需要的话，你应该阅读Tim Davis关于稀疏线性代数的书，下面是如何做稀疏矩阵乘法的方法。

通常的朴素稠密的乘法看起来是这样的。

C = 0
for i {
    for j {
        for k {
            C(i, j) = C(i, j) + (A(i, k) * B(k, j))
        }
    }
}

由于加法通勤，我们可以改变循环索引任何我们喜欢的方式。让我们把j最外层和i放在最里面。

C = 0
for j {
    for k {
        for i {
            C(i, j) = C(i, j) + (A(i, k) * B(k, j))
        }
    }
}

以CSC形式存储所有矩阵。由于j是最外层的，所以我们正在按时间编写B和C专栏(而不是A)。中间循环是在k上的，这是行B，非常方便，我们不需要访问为零的B条目。这使得外部两个循环按照自然顺序遍历B的非零项。内环将C的k第四列与A times B(k, j)的k第四列相加。为了简化这一操作，我们将C的当前列与该列为非零的一组索引一起密集地存储为一个list/稠密布尔数组。我们避免通过通常的隐式初始化技巧编写所有C或布尔数组。