Communication optimal parallel multiplication of sparse random matrices
Grey Ballard, Aydın Buluç, James Weldon Demmel, Laura Grigori, Benjamin Lipshitz, Oded Schwartz, Sivan Toledo · 2013
Parallel algorithms for sparse matrix-matrix multiplication typically spend most of their time on inter-processor communication rather than on computation, and hardware trends predict the relative cost of communication will only increase. Thus, sparse matrix multiplication algorithms must minimize communication costs in order to scale to large processor counts.