The Ubiquitous Sparse Matrix-Matrix Products

Aydin BuluçarXiv 2025 · DOI · arXiv

Introduction

Sparse matrix multiplication is the unsung workhorse of modern data science. While dense matrix multiplication (GEMM) receives the lion's share of attention in deep learning, real-world datasets—from social networks to quantum chemical systems—are predominantly sparse. This paper provides a comprehensive survey of sparse matrix-matrix multiplication (SpGEMM, SpMM, and SDDMM), framing these operations within a unified mathematical notation to highlight their essential role and guide future hardware and software optimizations.

The Problem: Bridging the Disconnect

The author identifies a significant disconnect in the research community: many new algorithms for sparse "matmul" are developed based on outdated motivations without verifying actual use cases. Unlike dense GEMM, sparse operations are notoriously difficult to optimize because their irregular structure leads to poor data reuse and complex memory access patterns. This paper aims to bridge that gap by identifying specific flavors of sparse multiplication used in practice, providing a "lens" for both application developers and hardware designers.

A Unified Mathematical Framework

The paper categorizes diverse sparse operations using a single unifying notation:

$$Y \leftarrow M \odot (AX)$$

In this expression, $M$ is a "mask" matrix and $\odot$ represents the Hadamard (element-wise) product. By varying the sparsity of $M, A,$ and $X$, we can define the key primitives that drive modern applications:

  • SpGEMM (Sparse-Sparse): Both $A$ and $X$ are sparse. This is the engine for graph analytics and scientific computing.
  • SpMM (Sparse-Dense): $A$ is sparse, while $X$ is a "tall-and-skinny" dense matrix. This kernel is the backbone of Graph Neural Networks (GNNs).
  • SDDMM (Sampled Dense-Dense): $A$ and $X$ are dense, but the output is only computed at indices specified by a sparse mask $M$. This is critical for efficient sparse attention in Transformer models.
The unified notation $Y \leftarrow M \odot (AX)$ for sparse matrix operations.

The framework also emphasizes the importance of semirings, where standard addition and multiplication are replaced by operations like "min" and "plus" (e.g., for shortest-path algorithms).

Key Insights and Applications

The utility of these kernels spans several domains:

  • Scientific Computing: SpGEMM is used for Algebraic Multigrid (AMG) solvers and linear-scaling quantum chemistry, while SpMM supports block iterative solvers.
  • Graph Analytics: SpGEMM enables efficient Betweenness Centrality and Triangle Counting.
  • Machine Learning: SpMM drives GNNs and recommendation models (DLRM), while SDDMM facilitates sparse attention in large language models.
  • Databases: A fascinating mapping exists between SpGEMM and database equi-joins, allowing database operations to leverage optimized linear algebra libraries.

Performance and the "Twilight Zone"

The paper highlights the "Twilight Zone" of sparsity—matrices that are 90-95% sparse. This level of sparsity is common in deep learning but presents a challenge: metadata (indices) can consume more memory than the data itself, especially in low-precision formats.

Quantitatively, SpMM is significantly easier to optimize than SpGEMM. On an NVIDIA P100 GPU, SpMM can reach over 1000 GFlops, whereas SpGEMM often struggles to break 100 GFlops. This performance gap stems from the higher operational intensity (OI) of SpMM, which allows for better data reuse.

Future Directions

To make sparsity truly "pay off" in next-generation AI models, future work must focus on index compression and hierarchical blocking. As we move toward FP8 and lower precisions, reducing the storage overhead of sparse indices becomes paramount. Additionally, the paper suggests that reinterpreting matrices as databases and utilizing randomized sketching will be key to managing massive datasets.

Summary updated

BibTeX
@misc{buluc2025ubiquitous,
  author = {Aydin Buluç},
  title = {{The Ubiquitous Sparse Matrix-Matrix Products}},
  year = {2025},
  eprint = {2508.04077},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2508.04077},
}
Figure