稀疏*密集矩阵乘法的运算次数
number of operations for sparse*dense matrix multiplication
使用优化的稀疏例程（如 cuSparse 或 Eigen 或 Matlab）乘以 CSR 稀疏 x 稠密矩阵或稠密 x CSR 稀疏矩阵需要多少次浮点运算。
在稀疏矩阵完全稠密的极限下，运算次数为N^2*(2*N-1) - 那么当稀疏矩阵不够稀疏时，为什么稀疏例程比稠密例程慢？正在做哪些额外的工作？
对于R += S * D，翻牌数是2*nnz(S)*ncols(D)，其中nnz代表非零数。
如果稀疏矩阵S变得密集，那么flops的数量与密集情况下的相同，但flops的数量并不是决定速度、内存访问的唯一标准通常更重要。首先，对于稀疏存储，每次访问 S 的元素都将花费额外的间接访问，例如：对于密集情况，value[p[k]] 而不是 value[i+j*N]。然后在密集的世界中出现了阻塞算法，以减少缓存未命中、矢量化 (SIMD) 和指令的最佳流水线，以达到 CPU 的最大性能。一个有效的密集矩阵乘积确实比朴素的 3 嵌套循环复杂几个数量级，你自己看看 Eigen 的 implementation。很可怕吧？
使用优化的稀疏例程（如 cuSparse 或 Eigen 或 Matlab）乘以 CSR 稀疏 x 稠密矩阵或稠密 x CSR 稀疏矩阵需要多少次浮点运算。
在稀疏矩阵完全稠密的极限下，运算次数为
N^2*(2*N-1)- 那么当稀疏矩阵不够稀疏时，为什么稀疏例程比稠密例程慢？正在做哪些额外的工作？
对于
R += S * D，翻牌数是2*nnz(S)*ncols(D)，其中nnz代表非零数。如果稀疏矩阵
S变得密集，那么flops的数量与密集情况下的相同，但flops的数量并不是决定速度、内存访问的唯一标准通常更重要。首先，对于稀疏存储，每次访问S的元素都将花费额外的间接访问，例如：对于密集情况，value[p[k]]而不是value[i+j*N]。然后在密集的世界中出现了阻塞算法，以减少缓存未命中、矢量化 (SIMD) 和指令的最佳流水线，以达到 CPU 的最大性能。一个有效的密集矩阵乘积确实比朴素的 3 嵌套循环复杂几个数量级，你自己看看 Eigen 的 implementation。很可怕吧？