The Ubiquitous Sparse Matrix-Matrix Products

2025/08/06 by Buluç, Aydın
#Combinatorics (math.CO) #Distributed #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Mathematical Software (cs.MS) #Numerical Analysis (math.NA) #Parallel #and Cluster Computing (cs.DC)

paper · doi:10.48550/arxiv.2508.04077

Abstract

Multiplication of a sparse matrix with another (dense or sparse) matrix is a fundamental operation that captures the computational patterns of many data science applications, including but not limited to graph algorithms, sparsely connected neural networks, graph neural networks, clustering, and many-to-many comparisons of biological sequencing data. In many application scenarios, the matrix multiplication takes places on an arbitrary algebraic semiring where the scalar operations are overloaded with user-defined functions with certain properties or a more general heterogenous algebra where even the domains of the input matrices can be different. Here, we provide a unifying treatment of the sparse matrix-matrix operation and its rich application space including machine learning, computational biology and chemistry, graph algorithms, and scientific computing.

Citations

• Toward Efficient SpMV in Sparse LLMs via Block Extraction and Compressed Storage
• Native Sparse Attention: Hardware-Aligned and Natively Trainable Sparse Attention
• An Efficient Sparse Kernel Generator for O(3)-Equivariant Deep Networks
• Interface for Sparse Linear Algebra Operations
• Distributed Matrix-Based Sampling for Graph Neural Network Training
• A fast, dense Chebyshev solver for electronic structure on GPUs
• Randomized Numerical Linear Algebra : A Perspective on the Field With an Eye to Software
• The Lazy Neuron Phenomenon: On Emergence of Activation Sparsity in Transformers
• FP8 Formats for Deep Learning
• MACE: Higher Order Equivariant Message Passing Neural Networks for Fast and Accurate Force Fields
• Distributed-Memory Sparse Kernels for Machine Learning
• High-order Line Graphs of Non-uniform Hypergraphs: Algorithms, Applications, and Experimental Analysis
• Enterprise-Scale Search: Accelerating Inference for Sparse Extreme Multi-Label Ranking Trees
• Accelerating Sparse Deep Neural Networks
• GPU Semiring Primitives for Sparse Neighborhood Methods
• Sparsity in Deep Learning: Pruning and growth for efficient inference\n and training in neural networks
• Parallel String Graph Construction and Transitive Reduction for De Novo Genome Assembly
• Distributed Many-to-Many Protein Sequence Alignment using Sparse Matrices
• FeatGraph: A Flexible and Efficient Backend for Graph Neural Network Systems
• Big Bird: Transformers for Longer Sequences
• GE-SpMM: General-purpose Sparse Matrix-Matrix Multiplication on GPUs for Graph Neural Networks
• Sparse GPU Kernels for Deep Learning
• The Hardware Lottery
• Longformer: The Long-Document Transformer
• CP2K: An electronic structure and molecular dynamics software package - Quickstep: Efficient and accurate electronic structure calculations
• Randomized Numerical Linear Algebra: Foundations & Algorithms
• Layer-Dependent Importance Sampling for Training Deep and Large Graph Convolutional Networks
• Deep Learning Recommendation Model for Personalization and Recommendation Systems
• The State of Sparsity in Deep Neural Networks
• On the Dimensionality of Embeddings for Sparse Features and Data
• How Powerful are Graph Neural Networks?
• The Convergence of Sparsified Gradient Methods
• Clebsch-Gordan Nets: a Fully Fourier Space Spherical Convolutional Neural Network
• Hierarchical Graph Representation Learning with Differentiable Pooling
• Tensor field networks: Rotation- and translation-equivariant neural networks for 3D point clouds
• Graph Attention Networks
• MPI-FAUN: An MPI-Based Framework for Alternating-Updating Nonnegative Matrix Factorization
• Scaling betweenness centrality using communication-efficient sparse matrix multiplication
• Reducing Parallel Communication in Algebraic Multigrid through Sparsification
• Sparse Tensor Algebra as a Parallel Programming Model
• OSNAP: Faster numerical linear algebra algorithms via sparser subspace\n embeddings
• Low-distortion Subspace Embeddings in Input-sparsity Time and Applications to Robust Linear Regression
• An Optimized Sparse Approximate Matrix Multiply for Matrices with Decay
• Sparser Johnson-Lindenstrauss Transforms
• A faster algorithm for betweenness centrality*
• Toward the Optimal Preconditioned Eigensolver: Locally Optimal Block Preconditioned Conjugate Gradient Method
• The Graph Neural Network Model

Related

• Graph Neural Networks and Applied Linear Algebra
• Approximating Sparse Matrices and their Functions using Matrix-vector products
• Hypergraph Partitioning for Sparse Matrix-Matrix Multiplication
• Sparse Matrix Factorization
• Low-Bandwidth Matrix Multiplication: Faster Algorithms and More General Forms of Sparsity