  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, with a modest preprocessing time,
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 for most of the tested data sets. This experimentally confirms the
provably effective theoretical bounds we show for our compressed-matrix
approach.
