# Common Subexpression-based Compression and Multiplication of Sparse Constant Matrices

arXiv: https://arxiv.org/abs/2303.16106 · HTML: https://mlsanity.com/paper/2303.16106/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 20 references that are in the map.
- First posted on arXiv 26 Mar 2023.

## Builds on (most cited first, 6 of 6)

- [A ConvNet for the 2020s](https://mlsanity.com/paper/2201.03545/) (2022)
- [Rethinking the Value of Network Pruning](https://mlsanity.com/paper/1810.05270/) (2018)
- [MCUNet: Tiny Deep Learning on IoT Devices](https://mlsanity.com/paper/2007.10319/) (2020)
- [Pruning and Quantization for Deep Neural Network Acceleration: A Survey](https://mlsanity.com/paper/2101.09671/) (2021)
- [Unrolling Ternary Neural Networks](https://mlsanity.com/paper/1909.04509/) (2019)
- [Tensor decomposition to Compress Convolutional Layers in Deep Learning](https://mlsanity.com/paper/2005.13746/) (2020)

## Abstract (arXiv)

In deep learning inference, model parameters are pruned and quantized to reduce the model size. Compression methods and common subexpression (CSE) elimination algorithms are applied on sparse constant matrices to deploy the models on low-cost embedded devices. However, the state-of-the-art CSE elimination methods do not scale well for handling large matrices. They reach hours for extracting CSEs in a 200 × 200 matrix while their matrix multiplication algorithms execute longer than the conventional matrix multiplication methods. Besides, there exist no compression methods for matrices utilizing CSEs. As a remedy to this problem, a random search-based algorithm is proposed in this paper to extract CSEs in the column pairs of a constant matrix. It produces an adder tree for a 1000 × 1000 matrix in a minute. To compress the adder tree, this paper presents a compression format by extending the Compressed Sparse Row (CSR) to include CSEs. While compression rates of more than 50% can be achieved compared to the original CSR format, simulations for a single-core embedded system show that the matrix multiplication execution time can be reduced by 20%.