您可以通过形成两个稀疏模式的乘积来模拟矩阵 - 矩阵乘积 - 即，您将稀疏模式（以 CSR 格式存储在单独的数组中）视为包含零或一的矩阵每个条目。执行此模拟产品只需要您形成和对这些 0 和 1 进行运算，因此比实际的矩阵-矩阵乘积要快得多——事实上，您所要做的就是遍历两个矩阵的行和列，并验证在 a 中至少有一个条目行和您相乘的列，其中两个矩阵均非零。这是一个便宜的操作——在任何情况下都比实际必须在实际产品中进行浮点乘法便宜得多，这不仅需要您进行浮点运算（昂贵），还需要从内存中读取实际的浮点数（甚至更昂贵，但在乘以稀疏模式时不需要它，因为矩阵的非零值单独存储在 CSR 中）。

我实际上在 Matlab 中为 A*B 编写了原始代码，A 和 B 都是稀疏的。为结果预先分配空间确实是有趣的部分。我们观察到 Godric 所指出的——知道 AB 中非零的数量与计算 AB 的成本一样高。

我们在 1990 年左右完成了稀疏 Matlab 的初步实现，在 Edith Cohen 论文给出了第一个实用、快速的方法来准确估计 AB 的大小之前。我们组合了一个较差的大小估计器，如果我们在计算过程中空间不足，则将分配加倍并复制部分计算的结果。

我不知道Matlab现在有什么。

另一种可能性是一次计算 AB 列。每列都可以临时存储在稀疏累加器中（有关这些的解释，请参见稀疏的 Matlab 论文），并分配空间来保存结果列的确切大小。结果将采用分散压缩的稀疏列形式——CSC 中的每一列但没有列间连续性——使用 2 个长度为 numcols（col start、col 长度）的向量，而不是一个向量作为元数据。它是一种可能值得一看的存储形式；它还有另一个优势——你可以在不重新分配整个矩阵的情况下增长一列。

本文描述了一种算法来近似两个稀疏矩阵的矩阵乘积的结果的大小。

在稀疏矩阵乘法中找到准确数量的非零条目的问题在于，结果中的每个元素都取决于两个向量的交互，这两个向量都可能至少包含一些非零元素。因此，要计算数字，您需要为结果中的每个元素评估一对向量的逻辑运算。这样做的问题在于，它需要的操作数与计算矩阵乘积本身所需的操作数相似。在我的评论中，我提到了在原始矩阵的非零元素中利用某些结构的可能性，但是这些相同的利用也可以用来减少矩阵乘法中所做的工作。

您最好使用上述论文来高估内存需求，进行乘法运算然后截断分配的内存，或者将结果矩阵移动到大小更合适的数组中。此外，稀疏矩阵产品并非罕见，我几乎可以保证这个问题之前已经解决了。稍微深入研究一些开源的稀疏矩阵库，应该会引导您了解它们用于预分配内存的算法。

对于 CSR 或 CSC，您是否保证您的矩阵元素数组已经没有零？在这种情况下，很容易找出有多少非零元素，使用类似于：

int nnz = sizeof(My_Array)/sizeof(long int);

但是，如果不是这种情况（似乎有点太容易），您可以尝试减少. 如果您的矩阵元素数组非常大，这可能是计算非零元素数量的最有效方法。许多并行 C/C++ 库，例如 Thrust（一个 CUDA 库）或 OpenCL（您不需要使用 GPU）都支持条件缩减 - 对于每个元素，添加Condition(Element). 如果您将条件设置为，Element != 0那么您将添加非零元素的数量。您可能还想从元素数组、行/列索引数组中删除零值元素，并调整列/行指针。