Return to search
## An I/O-Complexity Lower Bound for All Recursive Matrix Multiplication Algorithms by Path-Routing

<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.0113 seconds