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 "Strassenlike" 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, nonstationary" hybrid algorithms when executed in a twolevel storage hierarchy with M words of fast memory, where n_0 denotes the threshold size of subproblems which are computed using standard algorithms with algebraic complexity Omega (n^3).
The lower bound is actually derived for the more general class of "nonuniform, nonstationary" hybrid algorithms which allow recursive calls to have a different structure, even when they refer to the multiplication of matrices of the same size and in the same recursive level, although the quantitative expressions become more involved. Our results are the first I/O lower bounds for these classes of hybrid algorithms. All presented lower bounds apply even if the recomputation of partial results is allowed and are asymptotically tight.
The proof technique combines the analysis of the Grigoriev's flow of the matrix multiplication function, combinatorial properties of the encoding functions used by fast Strassenlike algorithms, and an application of the LoomisWhitney geometric theorem for the analysis of standard matrix multiplication algorithms. Extensions of the lower bounds for a parallel model with P processors are also discussed.
BibTeX  Entry
@InProceedings{destefani:LIPIcs:2019:11529,
author = {Lorenzo De Stefani},
title = {{The I/O Complexity of Hybrid Algorithms for Square Matrix Multiplication}},
booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)},
pages = {33:133:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771306},
ISSN = {18688969},
year = {2019},
volume = {149},
editor = {Pinyan Lu and Guochuan Zhang},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11529},
URN = {urn:nbn:de:0030drops115299},
doi = {10.4230/LIPIcs.ISAAC.2019.33},
annote = {Keywords: I/O complexity, Hybrid Algorithm, Matrix Multiplication, Recomputation}
}
Keywords: 

I/O complexity, Hybrid Algorithm, Matrix Multiplication, Recomputation 
Collection: 

30th International Symposium on Algorithms and Computation (ISAAC 2019) 
Issue Date: 

2019 
Date of publication: 

28.11.2019 