Parallel complexity of matrix multiplication

Research output: Contribution to journalArticlepeer-review


Effective design of parallel matrix multiplication algorithms relies on the consideration of many interdependent issues based on the underlying parallel machine or network upon which such algorithms will be implemented, as well as, the type of methodology utilized by an algorithm. In this paper, we determine the parallel complexity of multiplying two (not necessarily square) matrices on parallel distributed-memory machines and/or networks. In other words, we provided an achievable parallel run-time that can not be beaten by any algorithm (known or unknown) for solving this problem. In addition, any algorithm that claims to be optimal must attain this run-time. In order to obtain results that are general and useful throughout a span of machines, we base our results on the well-known LogP model. Furthermore, three important criteria must be considered in order to determine the running time of a parallel algorithm; namely, (i) local computational tasks, (ii) the initial data layout, and (iii) the communication schedule. We provide optimality results by first proving general lower bounds on parallel run-time. These lower bounds lead to significant insights on (i)-(iii) above. In particular, we present what types of data layouts and communication schedules are needed in order to obtain optimal run-times. We prove that no one data layout can achieve optimal running times for all cases. Instead, optimal layouts depend on the dimensions of each matrix, and on the number of processors. Lastly, optimal algorithms are provided.

Original languageEnglish (US)
Pages (from-to)155-175
Number of pages21
JournalJournal of Supercomputing
Issue number2
StatePublished - Jun 1 2003
Externally publishedYes


  • Linear algebra
  • LogP model
  • Lower bounds and optimality
  • Matrix multiplication
  • Numerical algorithms
  • Parallel algorithms
  • Parallel complexity
  • Parallel models

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Information Systems
  • Hardware and Architecture


Dive into the research topics of 'Parallel complexity of matrix multiplication'. Together they form a unique fingerprint.

Cite this