# Coded Sparse Matrix Multiplication

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Feb 2018.

## Built on by (most cited first, 3 of 3)

- [Straggler-Resilient Personalized Federated Learning](https://mlsanity.com/paper/2206.02078/) (2022)
- [Lightweight Projective Derivative Codes for Compressed Asynchronous Gradient Descent](https://mlsanity.com/paper/2201.12990/) (2022)
- [Random Alloy Codes and the Fundamental Limits of Coded Distributed Tensors](https://mlsanity.com/paper/2202.03469/) (2022)

## Abstract (arXiv)

In a large-scale and distributed matrix multiplication problem C=AintercalB, where C∈ℝr× t, the coded computation plays an important role to effectively deal with "stragglers" (distributed computations that may get delayed due to few slow or faulty processors). However, existing coded schemes could destroy the significant sparsity that exists in large-scale machine learning problems, and could result in much higher computation overhead, i.e., O(rt) decoding time. In this paper, we develop a new coded computation strategy, we call sparse code, which achieves near optimal recovery threshold, low computation overhead, and linear decoding time O(nnz(C)). We implement our scheme and demonstrate the advantage of the approach over both uncoded and current fastest coded strategies.