For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Greedy Approach Based Heuristics for Partitioning Sparse Matrices
Jiasen HUANG Junyan REN Wei LI
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2015/10/01
Online ISSN: 1745-1361
Type of Manuscript: LETTER
Category: Fundamentals of Information Systems
partitioning, greedy approach, recursive merging, highest mean density, lowest average relative difference,
Full Text: PDF(783KB)>>
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.