# Graph Expansion and Communication Costs of Fast Matrix Multiplication

### Grey Ballard, James Demmel, Olga Holtz and Oded Schwartz

###
EECS Department

University of California, Berkeley

Technical Report No. UCB/EECS-2011-40

May 6, 2011

### http://www.eecs.berkeley.edu/Pubs/TechRpts/2011/EECS-2011-40.pdf

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. For sequential algorithms these bounds are attainable and so tight.

**Author Comments:** The updated version can be found here: http://www.eecs.berkeley.edu/Pubs/TechRpts/2012/EECS-2012-194.html

BibTeX citation:

@techreport{Ballard:EECS-2011-40, Author = {Ballard, Grey and Demmel, James and Holtz, Olga and Schwartz, Oded}, Title = {Graph Expansion and Communication Costs of Fast Matrix Multiplication}, Institution = {EECS Department, University of California, Berkeley}, Year = {2011}, Month = {May}, URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2011/EECS-2011-40.html}, Number = {UCB/EECS-2011-40}, Note = {The updated version can be found here: http://www.eecs.berkeley.edu/Pubs/TechRpts/2012/EECS-2012-194.html}, 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. For sequential algorithms these bounds are attainable and so tight.} }

EndNote citation:

%0 Report %A Ballard, Grey %A Demmel, James %A Holtz, Olga %A Schwartz, Oded %T Graph Expansion and Communication Costs of Fast Matrix Multiplication %I EECS Department, University of California, Berkeley %D 2011 %8 May 6 %@ UCB/EECS-2011-40 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/2011/EECS-2011-40.html %F Ballard:EECS-2011-40