The I/O Complexity of Hybrid Algorithms for Square Matrix Multiplication

  • De Stefani, Lorenzo
Publication date
January 2019
Publisher
LIPIcs - Leibniz International Proceedings in Informatics. 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract

Asymptotically tight lower bounds are derived for the I/O complexity of a general class of hybrid algorithms computing the product of n x n square matrices combining "Strassen-like" fast matrix multiplication approach with computational complexity Theta(n^{log_2 7}), and "standard" matrix multiplication algorithms with computational complexity Omega (n^3). We present a novel and tight Omega ((n/max{sqrt M, n_0})^{log_2 7}(max{1,(n_0)/M})^3M) lower bound for the I/O complexity of a class of "uniform, non-stationary" hybrid algorithms when executed in a two-level storage hierarchy with M words of fast memory, where n_0 denotes the threshold size of sub-problems which are computed using standard algorithms with algebraic complexity Omega (n^3)...

Extracted data

Loading...

Related items

The I/O complexity of Strassenâs matrix multiplication with recomputation
  • BILARDI, GIANFRANCO
  • DE STEFANI, LORENZO
January 2017

A tight Ω((n/M ̅ ̅√)log27M) lower bound is derived on the I/O complexity of Strassen’s algorithm to ...

An I/O-Complexity Lower Bound for All Recursive Matrix Multiplication Algorithms by Path-Routing
  • Scott, Jacob N.
January 2015

Via novel path-routing techniques we prove a lower bound on the I/O-complexity of all recursive matr...

Using fast matrix multiplication to find basic solutions
  • Beling, Peter A.
  • Megiddo, Nimrod
September 1998

AbstractWe consider the problem of finding a basic solution to a system of linear constraints (in st...

We use cookies to provide a better user experience.