稀疏矩阵 - 矩阵乘法

Question

如何计算稀疏矩阵的矩阵乘积？我知道传统的数学方法，但似乎效率不高。有没有可以改进的方法？

我考虑过将第一个矩阵存储为CSR形式，第二个矩阵存储为CSC形式，因此由于行和列向量已排序，我不必搜索需要的特定行/列，但我想这并没有多大帮助。

- user3170713

---

这似乎是一个重复的问题 https://dev59.com/EXfZa4cB1Zd3GeqPPkmp - romants

在我看来，答案是否定的。那个问题是“是否有更适合矩阵-矩阵操作的更好的压缩格式”，而我要求的是更好的算法来实现两个矩阵的乘法运算。 - user3170713

Answer 1

在强调以下内容不应实现自己的稀疏矩阵包并且如果必须实现，应该先阅读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密集存储，并将这一列为非零的索引集合，作为一个列表/密集布尔数组。通过通常的隐式初始化技巧，我们避免编写整个C或布尔数组。

- David Eisenstat