### Graph expansion and communication costs of fast matrix multiplicationGraph expansion and communication costs of fast matrix multiplication

Access Restriction
Subscribed

 Author Ballard, Grey ♦ Demmel, James ♦ Holtz, Olga ♦ Schwartz, Oded Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2013 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Communication-avoiding algorithms ♦ I/O-complexity ♦ Fast matrix multiplication Abstract The communication cost of algorithms (also known as I/O-complexity) is shown to be closely related to the expansion properties of the corresponding computation graphs. We demonstrate this on Strassen's and other fast matrix multiplication algorithms, and obtain the first lower bounds on their communication costs. In the sequential case, where the processor has a fast memory of size $\textit{M},$ too small to store three $\textit{n}-by-\textit{n}$ matrices, the lower bound on the number of words moved between fast and slow memory is, for a large class of matrix multiplication algorithms, Ω( $(n/√M)^{ω_{0}}$ $·\textit{M}),$ where $ω_{0}$ is the exponent in the arithmetic count (e.g., $ω_{0}$ = lg 7 for Strassen, and $ω_{0}$ = 3 for conventional matrix multiplication). With $\textit{p}$ parallel processors, each with fast memory of size $\textit{M},$ the lower bound is asymptotically lower by a factor of $\textit{p}.$ These bounds are attainable both for sequential and for parallel algorithms and hence optimal. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2013-01-09 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 59 Issue Number 6 Page Count 23 Starting Page 1 Ending Page 23
Source: ACM Digital Library