Exploiting Multiple Levels of Parallelism in Sparse Matrix-Matrix Multiplication

DOI10.1137/15M104253XzbMath1350.05160arXiv1510.00844MaRDI QIDQ2833530

Grey Ballard, Ariful Azad, Laura Grigori, Aydın Buluç, Samuel Williams, Sivan Toledo, Oded Schwartz, James W. Demmel

Publication date: 18 November 2016

Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1510.00844

zbMATH Keywords

parallel computingnumerical linear algebragraph algorithmsmultithreading2.5D algorithms2D decomposition3D algorithmssparse matrix-matrix multiplicationSpGEMM

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Parallel algorithms in computer science (68W10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Memory-Efficient Sparse Matrix-Matrix Multiplication by Row Merging on Many-Core Architectures ⋮ A Novel Partitioning Method for Accelerating the Block Cimmino Algorithm ⋮ Efficient parallel linear scaling method to get the response density matrix in all-electron real-space density-functional perturbation theory ⋮ A distributed block Chebyshev-Davidson algorithm for parallel spectral clustering ⋮ Massively parallel sparse matrix function calculations with NTPoly ⋮ Fast matrix multiplication and its algebraic neighbourhood ⋮ Introduction to Communication Avoiding Algorithms for Direct Methods of Factorization in Linear Algebra ⋮ Unnamed Item ⋮ Sparse matrix multiplication and triangle listing in the congested clique model ⋮ Tail bounds for gaps between eigenvalues of sparse random matrices ⋮ Numerical algorithms for high-performance computational science ⋮ The parallelism motifs of genomic data analysis

Uses Software

• Trilinos
• SUMMA
• SparseMatrix
• symrcm
• SpAMM
• SpGEMM
• CSparse

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Communication lower bounds for distributed-memory matrix multiplication
• Optimizing Sparse Matrix—Matrix Multiplication for the GPU
• Simultaneous Input and Output Matrix Partitioning for Outer-Product--Parallel Sparse Matrix-Matrix Multiplication
• The university of Florida sparse matrix collection
• On Techniques to Improve Robustness and Scalability of a Parallel Hybrid Linear Solver
• Exposing Fine-Grained Parallelism in Algebraic Multigrid Methods
• Parallel Sparse Matrix-Matrix Multiplication and Indexing: Implementation and Experiments
• Direct Methods for Sparse Linear Systems
• Sparse Matrix-Matrix Products Executed Through Coloring
• GPU-Accelerated Sparse Matrix-Matrix Multiplication by Iterative Row Merging
• An overview of the Trilinos project
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• Parallel Matrix and Graph Algorithms
• Sparse Matrices in MATLAB: Design and Implementation
• Two Fast Algorithms for Sparse Matrices: Multiplication and Permuted Transposition
• An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations
• An Optimized Sparse Approximate Matrix Multiply for Matrices with Decay

This page was built for publication: Exploiting Multiple Levels of Parallelism in Sparse Matrix-Matrix Multiplication