稀疏*稠密矩阵乘法运算数

Question

1. 使用优化的稀疏例程(如cuSparse或特征或Matlab)乘CSR稀疏x密集矩阵或密集x CSR稀疏矩阵需要多少浮点运算。
2. 在稀疏矩阵完全密集的极限中，操作的数量是N^2*(2*N-1) --那么，当稀疏矩阵不够稀疏时，为什么稀疏例程比密集例程慢呢？正在进行哪些额外工作？

Answer 1

1. 对于R += S * D，失败数是2*nnz(S)*ncols(D)，nnz代表非零数。
2. 如果稀疏矩阵S变得密集，则触发器的数目与密集情况下相同，但触发器的数目不是决定速度的唯一判据，内存访问通常更重要。首先，对于稀疏存储，每次对S元素的访问都要花费额外的间接代价，比如：value[p[k]]而不是value[i+j*N]，用于密集的情况。然后在密集的世界中出现了阻塞算法，以减少缓存丢失、矢量化(SIMD)和指令的最优流水线，以达到CPU的最大性能。一个高效的稠密矩阵积确实比朴素的3个嵌套循环更复杂的数量级，您可以看到特征的实现。挺吓人的，不是吗？