More Like this

1. Distributed-Memory Parallel Algorithms for Sparse Matrix and Sparse Tall-and-Skinny Matrix Multiplication

   https://doi.org/10.1109/SC41406.2024.00052  

   Ranawaka, Isuru; Hussain, Md Taufique; Block, Charles; Gerogiannis, Gerasimos; Torrellas, Josep; Azad, Ariful (November 2024, IEEE)

   We consider a sparse matrix-matrix multiplication (SpGEMM) setting where one matrix is square and the other is tall and skinny. This special variant, TS-SpGEMM, has important applications in multi-source breadth-first search, influence maximization, sparse graph embedding, and algebraic multigrid solvers. Unfortunately, popular distributed algorithms like sparse SUMMA deliver suboptimal performance for TS-SpGEMM. To address this limitation, we develop a novel distributed-memory algorithm tailored for TS SpGEMM. Our approach employs customized 1D partitioning for all matrices involved and leverages sparsity-aware tiling for efficient data transfers. In addition, it minimizes communication overhead by incorporating both local and remote computations. On average, our TSSpGEMM algorithm attains 5x performance gains over 2D and 3D SUMMA. Furthermore, we use our algorithm to implement multi-source breadth-first search and sparse graph embedding algorithms and demonstrate their scalability up to 512 Nodes (or 65,536 cores) on NERSC Perlmutter. 

   more » « less
2. Adaptive sparse tiling for sparse matrix multiplication

   https://doi.org/10.1145/3293883.3295712  

   Hong, Changwan; Sukumaran-Rajam, Aravind; Nisa, Israt; Singh, Kunal; Sadayappan, P. (January 2019, Proceedings of the 24th ACM Symposium on Principles and Practice of Parallel Programming)
3. Efficient Tiled Sparse Matrix Multiplication through Matrix Signatures

   https://doi.org/10.1109/SC41405.2020.00091  

   Kurt, Sureyya Emre; Sukumaran-Rajam, Aravind; Rastello, Fabrice; Sadayappan, P. (November 2020, SC20: International Conference for High Performance Computing, Networking, Storage and Analysis)

   null (Ed.)
4. Sparsity-Aware Roofline Models for Sparse Matrix-Matrix Multiplication

   Qian, Matthew; Ramadan, Yahia; Anubha, Suhita; Azad, Ariful (May 2026, IEEE International Parallel and Distributed Processing Symposium (IPDPS))

   Sparse matrix–dense matrix multiplication (SpMM) is a critical kernel in scientific computing, graph analytics, and machine learning, whose performance is often constrained by memory bandwidth. In this work, we investigate the applicability and limitations of roofline modeling for SpMM by explicitly accounting for the impact of matrix sparsity structure on arithmetic intensity and attainable performance. We evaluate three SpMM implementations: Compressed Sparse Row (CSR), Compressed Sparse Blocks (CSB), and Intel's Math Kernel Library (MKL). Each implementation was tested using large-scale matrices from the SuiteSparse collection and grouped by sparsity pattern, including block-structured, banded (diagonal), scale-free, and uniformly random matrices. We derive sparsity-aware roofline models that incorporate memory traffic, cache locality, and blocking behavior, and demonstrate that a single model is insufficient to accurately predict performance across diverse structures. Experiments were conducted on an AMD-based Perlmutter compute node with a varying number of columns in the dense matrix. In particular, blocking and structured sparsity significantly alter effective arithmetic intensity. The results show that accurate roofline-based performance analysis of SpMM requires sparsity-aware modeling, and that data layout and blocking strategies must be evaluated in the context of matrix structure rather than through a single unified model. 

   more » « less
5. Statistical and computational limits for sparse matrix detection

   https://doi.org/10.1214/19-AOS1860  

   Cai, T. Tony; Wu, Yihong (June 2020, Annals of Statistics)

   null (Ed.)