2018/12/03 by Jonathan Eckstein, Eckstein, Jonathan, Gyorgy Matyasfalvi +1
Computer Science · #Advanced Data Storage Technologies #Distributed #Distributed and Parallel Computing Systems #FOS: Computer and information sciences #Mathematical Software (cs.MS) #Parallel #Parallel Computing and Optimization Techniques #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1812.00904
openalex publication_date 2018/12/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper presents an efficient technique for matrix-vector and vector-transpose-matrix multiplication in distributed-memory parallel computing environments, where the matrices are unstructured, sparse, and have a substantially larger number of columns than rows or vice versa. Our method allows for parallel I/O, does not require extensive preprocessing, and has the same communication complexity as matrix-vector multiplies with column or row partitioning. Our implementation of the method uses MPI. We partition the matrix by individual nonzero elements, rather than by row or column, and use an "overlapped" vector representation that is matched to the matrix. The transpose multiplies use matrix-specific MPI communicators and reductions that we show can be set up in an efficient manner. The proposed technique achieves a good work per processor balance even if some of the columns are dense, while keeping communication costs relatively low.