Sparse Matrix Multiplication in the Low-Bandwidth Model
Chetan Gupta, Juho Hirvonen, Janne H. Korhonen, Jan Studený, Jukka Suomela · 2022
We study matrix multiplication in the low-bandwidth model: There are n computers, and we need to compute the product of two n × n matrices. Initially computer i knows row i of each input matrix. In one communication round each computer can send and receive one O(logn)-bit message. Eventually computer i has to output row i of the product matrix.