Communication Optimal Parallel Multiplication of Sparse Random Matrices

Abstract

Parallel algorithms for sparse matrix-matrix multiplication typically spend most of their time on inter-processor communication rather than on computation, and hardware trends predict the relative cost of communication will only increase. Thus, sparse matrix multiplication algorithms must minimize communication costs in order to scale to large processor counts. In this paper, we consider multiplying sparse matrices corresponding to Erdos-Renyi random graphs on distributed-memory parallel machines. We prove a new lower bound on the expected communication cost for a wide class of algorithms. Our analysis of existing algorithms shows that, while some are optimal for a limited range of matrix density and number of processors, none is optimal in general. We obtain two new parallel algorithms and prove that they match the expected communication cost lower bound, and hence they are optimal.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Feb 21, 2013
Accession Number
ADA580140

Entities

People

  • Aydin Buluc
  • Benjamin Lipshitz
  • Grey Ballard
  • James Demmel
  • Laura Grigori
  • Oded Schwartz
  • Sivan Toledo

Organizations

  • University of California, Berkeley

Tags

DTIC Thesaurus Topics

  • Algebra
  • Algorithms
  • Bandwidth
  • Computations
  • Computer Science
  • Electrical Engineering
  • Engineering
  • Global Communications
  • Hard Copy
  • Humanities
  • Information Operations
  • Linear Algebra
  • Probability
  • Quantum Chemistry
  • Sparse Matrix
  • Stationary
  • Three Dimensional

Fields of Study

  • Computer science

Readers

  • Linear Algebra
  • Parallel and Distributed Computing.