Downsampling Algorithms for Large Sparse Matrices

作者：Langr Daniel^*; Tvrdik Pavel; Simecek Ivan; Dytrych Tomas

来源：International Journal of Parallel Programming, 2015, 43(5): 679-702.

DOI：10.1007/s10766-014-0315-8

• Downsampling
• Sparse matrix
• Matrix-processors mapping
• Distributed algorithm
• Parallel computing
• MPI
• Visualization

Mapping of sparse matrices to processors of a parallel system may have a significant impact on the development of sparse-matrix algorithms and, in effect, to their efficiency. We present and empirically compare two downsampling algorithms for sparse matrices. The first algorithm is independent of particular matrix-processors mapping, while the second one is adapted for cases where matrices are partitioned among processors according to contiguous chunks of rows/columns. We show that the price for the versatility of the first algorithm is the collective communication performed by all processors. The second algorithm uses more efficient communication strategy, which stems from the knowledge of mapping of matrices to processors, and effectively outperforms the first algorithm in terms of running time.

• 出版日期2015-10