Communication lower bounds for distributed-memory matrix multiplication
By Dror Irony, Sivan Toledo, A. Tiskin. 2004
285 citations recorded by the source corpus.
Subfields: Computational Theory and Mathematics, Computer Networks and Communications, Hardware and Architecture
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
- Edgar Solomonik
- K. Yelick
- J. Demmel
- Thomas Scanlon
- Oded Schwartz
- Shoaib Kamil
- Dmitriy Morozov
- Aydin Buluç
In Computer Networks and Communications
- J. Demmel
- Aydin Buluç
- K. Yelick
- Leonid Oliker
- Shoaib Kamil
- Penporn Koanantakool
- Oded Schwartz
- Thomas Scanlon
In Hardware and Architecture
- J. Demmel
- Aydin Buluç
- K. Yelick
- Leonid Oliker
- Shoaib Kamil
- Penporn Koanantakool
- Oded Schwartz
- Thomas Scanlon
Citations in the corpus
- Communication-optimal Parallel and Sequential QR and LU Factorizations (2008, background): “Thus, the lower bounds for communication by Hong and Kung [31] and by Irony, Toledo, and Tiskin [32] apply to LU decomposition as well.”
- A massively parallel tensor contraction framework for coupled-cluster computations (2014, background): “A few of the important differences between our work and this framework are overdecomposition and the redistribution mechanisms.”
- Communication lower bounds and optimal algorithms for programs that reference arrays - Part 1 (2013, methodology): “Recall from Section 2 that the problem of matrix multiplication was previously analyzed in [13] using the Loomis-Whitney inequality (Theorem 2.1, a special case of Theorem 3.2) and extended to many other linear algebra algorithms in [4].”
- Communication-Optimal Parallel 2.5D Matrix Multiplication and LU Factorization Algorithms (2011, background): “If this is the case, it is known that Cannon’s Algorithm [7] simultaneously balances the load (so F = Θ(n3/p)), minimizes the bandwidth cost (so W = Θ(n2/p1/2)), and minimizes the latency cost (so S = Θ(p1/2)) [15, 5].”
- Communication-Optimal Parallel Recursive Rectangular Matrix Multiplication (2013, methodology): “Each is benchmarked on three shapes of matrices corresponding to the three cases in the communication costs in Table I.”
- Communication-Avoiding Parallel Sparse-Dense Matrix-Matrix Multiplication (2016, background): “In the case of dense-dense matrix multiplication, both 2D and 3D algorithms are optimal, given their memory footprint [21].”