稀疏矩阵向量乘法的成本与非零条目的数量成线性关系，因为每个条目都与向量中的某个条目相乘一次。

稀疏矩阵-矩阵乘法的成本高度依赖于非零的结构。例如，考虑对稀疏矩阵进行平方$A$这是一个箭头结构：

$$A = \left(\begin{array}{ccccc} \delta_1 & & & & \beta_1 \\ & \delta_2 & & & \beta_2 \\ & & \ddots & & \vdots \\ & & & \delta_{n-1} & \beta_{n-1} \\ \gamma_1 & \gamma_2 & \cdots & \gamma_{n-1} & \delta_n \end{array}\right),$$

然后$A$拥有$O(n)$非零，但是$A^2$是稠密的。对这种现象有一个众所周知的图形解释：图中的每条长度为 1 或 2$A$成为图中的一条边$A^2$（即，一个非零条目$A^2$）。

首先，它依赖于实现。如果将稀疏矩阵实现为密集矩阵并填充非零，它将随矩阵的整体大小缩放。如果它被存储为非零，它将随着访问时间随矩阵大小而缩放。

在 PETSc 文档中，它解释了稀疏矩阵的默认存储是压缩行存储，它随行数和每行非零值的数量而缩放。因此，我希望 MatMat 可以随该度量的平方进行广泛缩放；IE$O(r^2 n^2)$.

然而，需要注意的一件事是，存储不存在的东西是没有意义的。如果您关心这种性能，为什么要为 1000x1000 矩阵存储 100 个值？这意味着至少 90% 的行/列根本没有非零值，并且可以完全从矩阵中删除。如果非零值的模式没有改变，请考虑从这个矩阵和目标矩阵中删除总是全零的行；它将消除大约 90% 的工作量，使两个矩阵 (100 ² , 1000 ² ) 的性能大致相当。

本文给出了一个完整的SpMV性能模型。它清楚地表明主要限制因素是带宽，尽管您可以通过使用多个向量来减轻负担。之后，您会遇到指令问题限制和我认为未完成的写入指令的限制。