Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

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