为什么稀疏密集乘法比密集稀疏乘法快？

Question

我很好奇为什么稀疏矩阵乘以稠密矩阵所用的时间与反向相乘所用的时间不同。算法有明显不同吗？

这是 matlab 2018a 中的示例：

a=sprand(M,M,0.01);
b=rand(M);
tic;ref1=a*b;t_axb=toc
tic;ref2=b*a;t_bxa=toc

这是一个使用 1 个线程的 Eigen 3 和 C++ 示例：

//prepare acol=MxM ColMajor Eigen sparse matrix with 0.01 density
...
Map<Matrix<double,M,M,ColMajor> > bcol (PR, M, M );
double tic,toc;

tic=getHighResolutionTime();
result=acol*bcol;
toc=getHighResolutionTime();
printf("\nacol*bcol time: %f seconds", (toc - tic));

tic=getHighResolutionTime();
result=bcol*acol;
toc=getHighResolutionTime();
printf("\nbcol*acol time: %f seconds\n", (toc - tic));

当M=4000时，结果为：

t_axb =
    0.6877
t_bxa =
    0.4803

acol*bcol time: 0.937590 seconds
bcol*acol time: 0.532622 seconds

当M=10000时，结果为

t_axb =
   11.5649
t_bxa =
    9.7872

acol*bcol time: 20.140380 seconds
bcol*acol time: 8.061626 seconds

在这两种情况下，对于 Matlab 和 Eigen，稀疏-密集积都比密集-稀疏积慢。我很好奇

为什么会这样？稀疏-密集算法与密集-稀疏算法有显着差异吗？ FLOP的个数是一样的吧？
为什么 eigen 匹配或超过 Matlab 的密集-稀疏乘积性能，而不是稀疏-密集乘积？性能上的微小差异是正常的，但考虑到两者都是高度优化的库，~1.4-1.8 的差异似乎很奇怪。我正在根据文档使用所有优化来编译本征。即 -fPIC -fomit-frame-pointer -O3 -DNDEBUG -fopenmp -march=native

Answer 1

通过比较稀疏矩阵乘积的列优先存储与行优先存储，您可以观察到相同的差异：y = A * x。如果 A 是行优先的（相当于 y 的每个系数），那么 A 的每一行都可以并行处理而没有任何开销（没有通信，没有额外的临时，没有额外的操作).相比之下，如果A是column-major，多线程就不是免费的，而且在大多数情况下是得不偿失的。

即使没有多线程，您也会看到内存访问模式非常不同：

行优先：对x的多次随机只读访问，y的每个系数都是只写一个。
Col-major：x 的每个 coeff 都被读取一次，但是我们得到了对目标 y.

所以即使没有多线程，情况自然也有利于行优先。

为什么稀疏密集乘法比密集稀疏乘法快？

Why is sparse-dense multiplication faster than dense-sparse multiplication?

matlab

algebra

sparse-matrix

eigen