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

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

这是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的性能，而对于稀疏产品而言， Eigen 值为什么不达到或超过Matlab的性能？性能上的微小差异是正常的，但是考虑到两者都是高度优化的库，差异约为1.4-1.8似乎很奇怪。我正在根据文档对 Eigen 进行所有优化。即-fPIC -fomit-frame-pointer -O3 -DNDEBUG -fopenmp -march=native

最佳答案

通过比较稀疏矩阵乘以向量乘积y = A * x的列主存储和行主存储，可以观察到相同的差异。如果A是行主要的(等效于y的每个系数)，则可以并行处理A的每一行，而不会产生任何开销(无需通信，无需额外的临时操作，无需额外的操作)。相反，如果A是主要列的多线程处理程序是不能免费获得的，那么在大多数情况下，开销要大于 yield 。

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

主要行:对x的多个随机只读访问，y的每个系数仅写入一个。

Col-major:x的每个系数都读取一次，但是我们对目标y进行了多次随机读写访问。

因此，即使没有多线程，这种情况自然也适合行优先。

关于matlab - 为什么稀疏-密集乘法比密集-稀疏乘法快？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/51461429/