<p> Via novel path-routing techniques we prove a lower bound on the I/O-complexity of all recursive matrix multiplication algorithms computed in serial or in parallel and show that it is tight for all square and near-square matrix multiplication algorithms. Previously, tight lower bounds were known only for the classical Θ (<i>n</i><sup>3</sup>) matrix multiplication algorithm and those similar to Strassen's algorithm that lack multiple vertex copying. We first prove tight lower bounds on the I/O-complexity of Strassen-like algorithms, under weaker assumptions, by constructing a routing of paths between the inputs and outputs of sufficiently small subcomputations in the algorithm's CDAG. We then further extend this result to all recursive divide-and-conquer matrix multiplication algorithms, and show that our lower bound is optimal for algorithms formed from square and nearly square recursive steps. This requires combining our new path-routing approach with a secondary routing based on the Loomis-Whitney Inequality technique used to prove the optimal I/O-complexity lower bound for classical matrix multiplication.</p>
| Identifer | oai:union.ndltd.org:PROQUEST/oai:pqdtoai.proquest.com:10086162 |
| Date | 08 April 2016 |
| Creators | Scott, Jacob N. |
| Publisher | University of California, Berkeley |
| Source Sets | ProQuest.com |
| Language | English |
| Detected Language | English |
| Type | thesis |
Page generated in 0.002 seconds