Name
Abstract | ||
|---|---|---|
We apply a novel technique based on path routings to obtain optimal I/O-complexity lower bounds for all Strassen-like fast matrix multiplication algorithms computed in serial or in parallel, assuming no reuse of nontrivial intermediate linear combinations. Given fast memory of size M, we prove an I/O-complexity lower bound of Ω((n/√M}ω0 • M) for any Strassen-like matrix multiplication algorithm applied to n x n matrices of arithmetic complexity Θ(nω0) with ω0 |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1145/2755573.2755594 | ACM Symposium on Parallelism in Algorithms and Architectures |
Keywords | Field | DocType |
Communication-avoiding algorithms,Fast matrix multiplication,I/O-complexity | Linear combination,Discrete mathematics,Communication-avoiding algorithms,Combinatorics,Multiplication algorithm,Matrix (mathematics),Upper and lower bounds,Input/output,Matrix multiplication,Mathematics | Conference |
Citations | PageRank | References |
5 | 0.42 | 11 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jacob Scott | 1 | 151 | 14.00 |
| Olga Holtz | 2 | 308 | 18.88 |
| Oded Schwartz | 3 | 516 | 33.91 |