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. 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.)
5. Iterative Collaborative Filtering for Sparse Matrix Estimation

   https://doi.org/10.1287/opre.2021.2193  

   Borgs, Christian; Chayes, Jennifer T.; Shah, Devavrat; Yu, Christina Lee (December 2021, Operations Research)

   We consider sparse matrix estimation where the goal is to estimate an n-by-n matrix from noisy observations of a small subset of its entries. We analyze the estimation error of the popularly used collaborative filtering algorithm for the sparse regime. Specifically, we propose a novel iterative variant of the algorithm, adapted to handle the setting of sparse observations. We establish that as long as the number of entries observed at random scale logarithmically larger than linear in n, the estimation error with respect to the entry-wise max norm decays to zero as n goes to infinity, assuming the underlying matrix of interest has constant rank r. Our result is robust to model misspecification in that if the underlying matrix is approximately rank r, then the estimation error decays to the approximation error with respect to the [Formula: see text]-norm. In the process, we establish the algorithm’s ability to handle arbitrary bounded noise in the observations. 

   more » « less