2021/11/18 by Srđan Milaković, Oguz Selvitopi, Oğuz Selvitopi +9 · 1 citation
Computer Science · #Advanced Graph Neural Networks #Data Structures and Algorithms (cs.DS) #Distributed #Error Correcting Code Techniques #FOS: Computer and information sciences #Graph Theory and Algorithms #Mathematical Software (cs.MS) #Parallel #and Cluster Computing (cs.DC) #cs.DC #cs.DS #cs.MS
paper · pdf · doi:10.48550/arxiv.2111.09947
arxiv created 2021/11/18 · openalex publication_date 2021/11/18 · arxiv updated 2021/11/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Computing the product of two sparse matrices (SpGEMM) is a fundamental operation in various combinatorial and graph algorithms as well as various bioinformatics and data analytics applications for computing inner-product similarities. For an important class of algorithms, only a subset of the output entries are needed, and the resulting operation is known as Masked SpGEMM since a subset of the output entries is considered to be "masked out". Existing algorithms for Masked SpGEMM usually do not consider mask as part of multiplication and either first compute a regular SpGEMM followed by masking, or perform a sparse inner product only for output elements that are not masked out. In this work, we investigate various novel algorithms and data structures for this rather challenging and important computation, and provide guidelines on how to design a fast Masked-SpGEMM for shared-memory architectures. Our evaluations show that factors such as matrix and mask density, mask structure and cache behavior play a vital role in attaining high performance for Masked SpGEMM. We evaluate our algorithms on a large number of matrices using several real-world benchmarks and show that our algorithms in most cases significantly outperform the state of the art for Masked SpGEMM implementations.