×

Graph expansion analysis for communication costs of fast rectangular matrix multiplication. (English) Zbl 1385.68057

Even, Guy (ed.) et al., Design and analysis of algorithms. First Mediterranean conference on algorithms, MedAlg 2012, Kibbutz Ein Gedi, Israel, December 3–5, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-34861-7/pbk). Lecture Notes in Computer Science 7659, 13-36 (2012).
Summary: Graph expansion analysis of computational DAGs is useful for obtaining communication cost lower bounds where previous methods, such as geometric embedding, are not applicable. This has recently been demonstrated for Strassen’s and Strassen-like fast square matrix multiplication algorithms. Here we extend the expansion analysis approach to fast algorithms for rectangular matrix multiplication, obtaining a new class of communication cost lower bounds. These apply, for example to the algorithms of D. Bini et al. [Inf. Process. Lett. 8, 234–235 (1979; Zbl 0395.68048)] and the algorithms of J. E. Hopcroft and L. R. Kerr [SIAM J. Appl. Math. 20, 30–36 (1971; Zbl 0215.55501)]. Some of our bounds are proved to be optimal.
For the entire collection see [Zbl 1259.68004].

MSC:

68W40 Analysis of algorithms
68W30 Symbolic computation and algebraic computation
PDFBibTeX XMLCite
Full Text: DOI arXiv arXiv