我最近遇到了这篇论文，它描述了一种在表示稀疏矩阵时节省内存的方案。一个 32 位整数最多可以存储约 40 亿个数字。但是当你解决一个偏微分方程时，你已经在未知数接近 40 亿之前就已经并行化并划分了问题。他们的想法是为小带宽重新排序矩阵。它们不是存储j给定行中所有非零列的索引，而是存储i偏移量j - i，由于重新排序，偏移量往往很小。然后可以使用比 32 位整数更少的位来存储偏移量。迭代矩阵的非零条目时需要做更多的算术运算，但减少缓存未命中的节省远远超过了弥补。在这篇论文中他们专门研究在分层矩阵格式中使用 16 位索引，但最终这是一个类似的想法。还有库zfp，它更多地用于压缩浮点数据。
由于现在“触发器是免费的”并且瓶颈是内存访问，因此这些技巧似乎真的很有希望更好地利用 CPU 缓存。
我已经搜索了这两篇论文的大部分被引用/引用的作品。我正在寻找关于位打包有效性、稀疏矩阵向量乘法和计算科学中任何其他问题的任何其他参考资料。例如，我想你可以使用这个想法为图形或非结构化网格设计更有效的数据结构。
一种方法（他们在您链接的第一篇论文中提到，但值得强调）是块压缩稀疏行 (BCSR) 存储格式。如果您的问题造成密集块（例如在每个节点具有多个自由度的 FEM 中很常见），您修改典型的 CSR (CSC) 存储方案以仅存储块的单个列（行）索引。这将索引向量的存储需求减少了一个因子. 如果你要存储块，这将索引向量所需的内存减少了约 90%，这比使用任何类型的位打包技巧节省的内存要多得多。
可以在这里找到更完整的格式描述：http: //www.netlib.org/utk/people/JackDongarra/etemplates/node375.html
此外，在稀疏矩阵中存储密集块允许您使用 SSE 或 AVX 指令对矩阵向量乘法进行向量化，但您可能不会在这里看到巨大的加速，因为正如您所指出的，您仍然会受到内存限制.
如果您的问题没有产生像 FEM 一样完美的 BCSR 结构，那么您仍然可以使用该技术而不会产生未对齐块的内存开销。本文展示了一个不需要块以多个列（并且还解释了我所说的未对齐块的内存开销的意思）。
https://bebop.cs.berkeley.edu/pubs/vuduc2005-ubcsr-split.pdf
当然，没有什么可以阻止您使用重新排序的 BCSR 矩阵来玩位打包游戏以进一步降低内存需求，但您可能应该先选择容易实现的目标。
如果您对位打包的应用特别感兴趣，这在 LLVM 项目中非常积极。它的一个（聪明？）想法是使用他们所谓的 PointerIntPair，它将一个指针和一个小整数一起存储在单个指针的空间中。这里的想法是利用这一事实（在 linux x64 系统上），malloc 返回的指针是 16 字节对齐的，这使您在底部有 4 位可以处理。他们使用这个想法做各种疯狂的事情，构建复杂的数据结构，这些数据结构存在于单个指针的空间中。这是几年前由 LLVM 优化器专家之一进行的一次有趣的会议演讲。他在 22:00 开始谈论这个问题。不过，公平的警告是：这是在一个 C++ 会议上，因此涉及到大量毫不掩饰的复杂 C++。
https://www.youtube.com/watch?v=vElZc6zSIXM&t=22m&ab_channel=CppCon