I recently came across this paper, which describes a scheme for saving memory in representing sparse matrices. A 32-bit integer can store numbers up to ~4 billion. But when you solve a PDE you've gone parallel and partitioned the problem long before the number of unknowns is anywhere close to 4 billion. Their idea is to reorder the matrix for small bandwidth. Rather than store the indices
j of all non-zero columns in a given row
i, they store the offset
j - i, which tends to be small in magnitude by virtue of the reordering. The offsets can then be stored using fewer bits than a 32-bit integer would. There's more arithmetic to do when iterating over the non-zero entries of the matrix, but the savings in fewer cache misses more than make up for it. In this paper they were looking specifically at using 16-bit indices in a hierarchical matrix format, but ultimately it's a similar idea. There's also the library zfp, which is more for compressing floating-point data.
Since "flops are free" now and the bottleneck is memory access, these kinds of tricks seem really promising for making better use of CPU cache.
I've scoured most of the cited/citing works of these two papers. I'm looking for any other references on the effectiveness of bit-packing, for sparse matrix-vector multiplication and for any other problems in computational science. For example, I imagine you could design much more efficient data structures for graphs or for unstructured meshes using this idea.