Greedy Approach Based Heuristics for Partitioning Sparse Matrices

DOI Web Site 10 References
  • REN Junyan
    State-Key Laboratory of ASIC and Systems, Fudan University
  • HUANG Jiasen
    State-Key Laboratory of ASIC and Systems, Fudan University
  • LI Wei
    State-Key Laboratory of ASIC and Systems, Fudan University

Bibliographic Information

Published
2015
DOI
  • 10.1587/transinf.2015edl8088
Publisher
The Institute of Electronics, Information and Communication Engineers

Search this article

Description

Sparse Matrix-Vector Multiplication (SpMxV) is widely used in many high-performance computing applications, including information retrieval, medical imaging, and economic modeling. To eliminate the overhead of zero padding in SpMxV, prior works have focused on partitioning a sparse matrix into row vectors sets (RVS's) or sub-matrices. However, performance was still degraded due to the sparsity pattern of a sparse matrix. In this letter, we propose a heuristics, called recursive merging, which uses a greedy approach to recursively merge those row vectors of nonzeros in a matrix into the RVS's, such that each set included is ensured a local optimal solution. For ten uneven benchmark matrices from the University of Florida Sparse Matrix Collection, our proposed partitioning algorithm is always identified as the method with the highest mean density (over 96%), but with the lowest average relative difference (below 0.07%) over computing powers.

Journal

References(10)*help

See more

Keywords

Details 詳細情報について

Report a problem

Back to top