Grey Ballard and James Demmel and Olga Holtz and Oded Schwartz

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2011-40

May 6, 2011

http://www2.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.

---

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},
    Year= {2011},
    Month= {May},
    Url= {http://www2.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://www2.eecs.berkeley.edu/Pubs/TechRpts/2011/EECS-2011-40.html
%F Ballard:EECS-2011-40