我有以下情况：我有一个向量序列并且对于每个我想计算的乘积，其中一开始是固定的。尽管没有关于结构的信息，通常具有重复许多值的特定模式，我想尽快计算这些乘积。
一个示例如下所示：
这里的白色区域是 0。
我想知道是否有某种方法可以存储有关的信息或以某种方式对其进行修改，以减少每个产品的操作次数。对于全为 0 的行，这是微不足道的——可以只存储指示此类行的行索引。还可以存储有关哪些行重复的信息，以便重用行计算。我还考虑过对矩阵的行进行排序，例如最小化每行之间的平均差异，并且只计算每行的差异。然而，对于更复杂的模式，这似乎遇到了问题。
我想知道这些问题是否有任何已知的方法。
编辑：我的另一个想法是，因为没有。矩阵中唯一值的数量相当低，可以将产品分解为其中仅包含一个唯一值，但我仍然不确定这是否可以为这个问题提供任何优势。
我提出一个不同的观点。也许你可以通过一些巧妙的矩阵乘法来提高性能，但有不止一种可能性是你得到的结果很小。
这种矩阵很小，我们说的是，现代 cpu 有很大的功率，在这个大小上工作没有问题。瓶颈是将数据移动到cpu。Blas库已经解决了这类问题。Blas 库不仅关注乘法，还关注如何优化在硬件内部移动的数据。
要想获得 Blas 函数的最佳性能，这对我们来说几乎是不可能的，这是非常困难的。经典的例子是嵌套循环。例如，安装了 Blas 的Atlas的特定实现会自动调整硬件（请参阅此 pdf）。
由于这些原因，我告诉你的第一个建议是尝试使用 Blas 库。有关列表，请参阅之前的 wiki 页面，有商业的或免费的，这取决于你（也许你可以从 OpenBlas 开始）。请注意，它们下也有使用 Blas 的库，它们更舒适。
如果这还不够，请尝试其他方式，但请记住使用 Blas 进行乘法运算。
如果零元素的数量越来越多，情况就不同了，不是这样，给出一个大约 90% 的概念。在这里你有稀疏矩阵，你可以使用不同的存储方法来获得优势。请注意，在这种情况下，您也可以找到稀疏的 Blas。
免责声明：我不知道这是否真的会加快您的计算，因为它会增加相当多的计算开销。由于您的矩阵看起来不是很稀疏，因此很难想象击败英特尔 MKL之类的BLAS实现。
也就是说，这是一个想法：
存储一个稀疏矩阵数组，每个矩阵中的每个唯一值都有一个，其中每个稀疏矩阵都以压缩行格式存储。这里的聪明之处在于您不需要实际存储稀疏矩阵条目（来自维基百科文章），只有稀疏模式和因为矩阵条目都是一样的。当使用这些稀疏矩阵之一执行矩阵向量乘积时，您只需要将向量中的条目相加因为乘法可以在最后发生。
如果矩阵中有一些没有重复的值，则可以将它们全部放入一个常规的稀疏矩阵中，并以“正常”稀疏矩阵的方式执行 MVP。
显然，这种方法的实现并非易事。即使它比直接的 BLAS 实现更快，您也可能需要有很多向量来补偿稀疏矩阵设置中的计算开销。我确实认为这种方法可以节省相当多的存储空间，这是值得的。