Graph Expansion and Communication Costs of Fast Matrix Multiplication

Grey Ballard, James Demmel, Olga Holtz +1

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 demonstra…