282 citations · 955 across the 31 of their papers we have counts for
4 papers · 1 filter
Graph Expansion Analysis for Communication Costs of Fast Rectangular Matrix Multiplication
Grey Ballard, James Demmel, Olga Holtz +2
Graph expansion analysis of computational DAGs is useful for obtaining communication cost lower bounds where previous methods, such as geometric embedding, are not applicable. This…
Strong Scaling of Matrix Multiplication Algorithms and Memory-Independent Communication Lower Bounds
Grey Ballard, James Demmel, Olga Holtz +2
A parallel algorithm has perfect strong scaling if its running time on P processors is linear in 1/P, including all communication costs. Distributed-memory parallel algorithms for…
Communication-Optimal Parallel Algorithm for Strassen's Matrix Multiplication
Grey Ballard, James Demmel, Olga Holtz +2
Parallel matrix multiplication is one of the most studied fundamental problems in distributed and high performance computing. We obtain a new parallel algorithm that is based on St…
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…