Optimizing Compression Schemes for Parallel Sparse Tensor Algebra

This paper studies compression techniques for parallel in-memory sparse tensor algebra. We find that applying simple existing compression schemes can lead to performance loss in some cases. To resolve this issue, we introduce an optimized algorithm for processing compressed inputs that can improve both the space usage as well as the performance compared to uncompressed inputs. We implement the compression techniques on top of a suite of sparse matrix algorithms generated by taco, a compiler for sparse tensor algebra. On a machine with 48 hyperthreads, our empirical evaluation shows that compression reduces the space needed to store the matrices by over 2x without sacrificing algorithm performance.