Imperial College London
In this paper, the authors present a new graph model of sparse matrix decomposition for parallel sparse matrix - vector multiplication. Their model differs from previous graph-based approaches in two main respects. Firstly, their model is based on edge coloring rather than vertex partitioning. Secondly, their model is able to correctly quantify and minimize the total communication volume of the parallel sparse matrix - vector multiplication while maintaining the computational load balance across the processors.