Greedy Approach Based Heuristics for Partitioning Sparse Matrices

Jiasen HUANG  Junyan REN  Wei LI  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E98-D   No.10   pp.1847-1851
Publication Date: 2015/10/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2015EDL8088
Type of Manuscript: LETTER
Category: Fundamentals of Information Systems
Keyword: 
partitioning,  greedy approach,  recursive merging,  highest mean density,  lowest average relative difference,  

Full Text: PDF(783KB)>>
Buy this Article




Summary: 
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.