A tight Ω((n/M‾‾√)log27M) lower bound is derived on the I/O complexity of Strassen’s algorithm to multiply two n×n matrices, in a two-level storage hierarchy with M words of fast memory. A proof technique is introduced, which exploits the Grigoriev’s flow of the matrix multiplication function as well as some combinatorial properties of the Strassen computational directed acyclic graph (CDAG). Applications to parallel computation are also developed. The result generalizes a similar bound previously obtained under the constraint of no-recomputation, that is, that intermediate results cannot be computed more than once.
The I/O complexity of Strassenâs matrix multiplication with recomputation
BILARDI, GIANFRANCO;DE STEFANI, LORENZO
2017
Abstract
A tight Ω((n/M‾‾√)log27M) lower bound is derived on the I/O complexity of Strassen’s algorithm to multiply two n×n matrices, in a two-level storage hierarchy with M words of fast memory. A proof technique is introduced, which exploits the Grigoriev’s flow of the matrix multiplication function as well as some combinatorial properties of the Strassen computational directed acyclic graph (CDAG). Applications to parallel computation are also developed. The result generalizes a similar bound previously obtained under the constraint of no-recomputation, that is, that intermediate results cannot be computed more than once.File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
Bilardi_DeStefani.pdf
accesso aperto
Descrizione: Articollo
Tipologia:
Postprint (accepted version)
Licenza:
Accesso gratuito
Dimensione
350.35 kB
Formato
Adobe PDF
|
350.35 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
