2016/05/07 by Gianfranco Bilardi, Bilardi, Gianfranco, Lorenzo De Stefani +1
Computer Science · #68W40 #Cellular Automata and Applications #Computability, Logic, AI Algorithms #Data Structures and Algorithms (cs.DS) #F.2.1 #FOS: Computer and information sciences #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1605.02224
openalex publication_date 2016/05/07 · openalex created_date 2022/09/26 · openalex updated_date 2026/07/28
A tight \Ω((n/\√(M))\log2 7M) lower bound is derived on the io\ncomplexity of Strassen's algorithm to multiply two n \× n matrices, in a\ntwo-level storage hierarchy with M words of fast memory. A proof technique is\nintroduced, which exploits the Grigoriev's flow of the matrix multiplication\nfunction as well as some combinatorial properties of the Strassen computational\ndirected acyclic graph (CDAG). Applications to parallel computation are also\ndeveloped. The result generalizes a similar bound previously obtained under the\nconstraint of no-recomputation, that is, that intermediate results cannot be\ncomputed more than once. For this restricted case, another lower bound\ntechnique is presented, which leads to a simpler analysis of the io complexity\nof Strassen's algorithm and can be readily extended to other "Strassen-like"\nalgorithms.\n