On Parallelizing Matrix Multiplication by the Column-Row Method

We consider the problem of sparse matrix multiplication by the column row method in a distributed setting where the matrix product is not necessarily sparse. We present a sur-prisingly simple method for “consistent ” parallel process-ing of sparse outer products (column-row vector products) over several processors, in a communication-avoiding setting where each processor has a copy of the input. The method is consistent in the sense that a given output entry is al-ways assigned to the same processor independently of the specific structure of the outer product. We show guaran-tees on the work done by each processor, and achieve linear speedup down to the point where the cost is dominated by reading the input. Our method gives a way of distributing (or parallelizing) matrix product computations in settings where the main bottlenecks are storing the result matrix, and inter-processor communication. Motivated by observa-tions on real data that often the absolute values of the entries in the product adhere to a power law, we combine our ap-proach with frequent items mining algorithms and show how to obtain a tight approximation of the weight of the heaviest entries in the product matrix. As a case study we present the application of our approach to frequent pair mining in transactional data streams, a prob-lem that can be phrased in terms of sparse {0, 1}-integer matrix multiplication by the column-row method. Experi-mental evaluation of the proposed method on real-life data supports the theoretical findings.