algorithm - 稀疏矩阵——矩阵乘法

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 的第 j 列增加 A 的第 k 倍 B (k, j)。为简化此操作，我们将 C 的当前列连同该列非零的索引集一起存储为列表/密集 bool 数组。我们避免通过通常的隐式初始化技巧编写所有 C 或 bool 数组。