# A sparsity-aware distributed-memory algorithm for sparse-sparse matrix multiplication

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Aug 2024.

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

- [Slicing Is All You Need: Towards A Universal One-Sided Algorithm for Distributed Matrix Multiplication](https://mlsanity.com/paper/2510.08874/) (2025)
- [Communication-Avoiding Linear Algebraic Kernel K-Means on GPUs](https://mlsanity.com/paper/2601.17136/) (2026)

## Abstract (arXiv)

Multiplying two sparse matrices (SpGEMM) is a common computational primitive used in many areas including graph algorithms, bioinformatics, algebraic multigrid solvers, and randomized sketching. Distributed-memory parallel algorithms for SpGEMM have mainly focused on sparsity-oblivious approaches that use 2D and 3D partitioning. Sparsity-aware 1D algorithms can theoretically reduce communication by not fetching nonzeros of the sparse matrices that do not participate in the multiplication. Here, we present a distributed-memory 1D SpGEMM algorithm and implementation. It uses MPI RDMA operations to mitigate the cost of packing/unpacking submatrices for communication, and it uses a block fetching strategy to avoid excessive fine-grained messaging. Our results show that our 1D implementation outperforms state-of-the-art 2D and 3D implementations within CombBLAS for many configurations, inputs, and use cases, while remaining conceptually simpler.