###
Improving Matrix-vector Multiplication via Lossless Grammar-Compressed
Matrices

####
Paolo Ferragina, Giovanni Manzini, Travis Gagie, Dominik Köppl,
Gonzalo Navarro, Manuel Striani, and Francesco Tosoni

As nowadays Machine Learning (ML) techniques are generating
huge data collections, the problem of how to efficiently engineer
their storage and operations is becoming of paramount importance.
In this article we propose a new lossless compression scheme for
real-valued matrices which achieves efficient performance in terms
of compression ratio and time for linear-algebra operations.
Experiments show that, as a compressor, our tool is clearly superior
to gzip and it is usually within 20% of xz in terms of compression
ratio. In addition, our compressed format supports matrix-vector
multiplications in time and space proportional to the size of the
compressed representation, unlike gzip and xz that require the full
decompression of the compressed matrix. To our knowledge our
lossless compressor is the first one achieving time and space
complexities which match the theoretical limit expressed by the k-th
order statistical entropy of the input.
To achieve further time/space reductions, we propose column-reordering
algorithms hinging on a novel column-similarity score.
Our experiments on various data sets of ML matrices show that our
column reordering can yield a further reduction of up to 16% in the
peak memory usage during matrix-vector multiplication.

Finally, we compare our proposal against the state-of-the-art
Compressed Linear Algebra (CLA) approach showing that ours runs
always at least twice faster (in a multi-thread setting), and achieves
better compressed space occupancy and peak memory usage. This
experimentally confirms the provably effective theoretical bounds
we show for our compressed-matrix approach.