对于它的价值，对于大小为 10,000 x 10,000 的随机稀疏矩阵与相同大小的密集矩阵，在我使用 MATLAB 和英特尔 MKL 作为 BLAS 的至强工作站上，稀疏矩阵向量乘法在 15% 的密度下更快或更少。在 67% 时（如另一个答案所建议的），密集矩阵向量乘法大约快三倍。

在当今的处理器上，所有矩阵运算都受内存限制（而不是计算限制）。所以基本上，您必须询问哪种格式存储的字节数更少。这很容易计算：

• 对于一个完整的矩阵，每个条目存储 8 个字节（一个双字节）
• 对于稀疏矩阵，每个条目存储 12 个字节（一个 double 用于值，一个整数用于条目的列索引）。

换句话说，如果您的稀疏度低于 67%（即，对于几乎任何合理的人都会称之为稀疏的任何矩阵），稀疏矩阵格式不仅会产生更好的内存使用，而且会产生更好的计算时间。

即使一个矩阵非常稀疏，它与自身的矩阵乘积也可以是稠密的。以对角矩阵为例，并用非零项填充其第一行和第一列；它与自身的产品将是完全密集的。例如，这样的矩阵可以作为图的拉普拉斯算子出现，其中有一个顶点连接到所有其他顶点。在实践中，只要有几个顶点与网络的其余部分具有相当高的连接性就足够了。对于矩阵向量乘法，这种现象不太相关，尽管在尝试并行化矩阵向量乘法时可能会导致不平衡。

我要强调的是：这实际上取决于稀疏模式以及您想对矩阵做什么。因此，我能想出的稀疏矩阵的最佳定义（同时也没什么用）如下：

如果仅存储其非零值及其位置并投入来自管理产生的数据结构的额外开销是有利的，则矩阵是稀疏的。

要学习的教训：这真的取决于你想用它做什么，你使用哪种算法，以及（正如其他人已经指出的）你使用的硬件和软件是否给定矩阵是稀疏的（读作：是否应该使用稀疏或密集矩阵数据结构）。如果不仅仅是关于存储数据或矩阵向量乘法，则不可能有纯粹基于百分比的规则。找出矩阵是否稀疏的最佳方法就是尝试并与密集矩阵方法进行比较。