稀疏矩阵乘法的复杂度

Question

我想表达两种算法的计算复杂度: 稀疏矩阵稀疏向量乘法和稀疏矩阵稀疏矩阵乘法，这些算法使用CSR表示在Eigen或Cusparse中实现。

我知道这取决于几个参数，特别是每个元素中非零值的数量。

然而，我找不到详细说明此类算法复杂度并使用O()符号表达的出版物。

- Oran

Answer 1

假设您正在使用A是一个m*k的矩阵，每列有a个非零元素，并且B是一个k*n的矩阵，每列有b个非零元素来乘以A*B。那么，(*和+)操作的数量为：

2*n*b*a

因为对于B的每个列，我们必须循环遍历相应的非零元素的A列进行乘累加操作。如果像Eigen或Cusparse这样正确实现，我们会有三个嵌套循环，分别是n、b和a次迭代，因此复杂度是O(a*b*n)。

- ggael