Greedy Approach Based Heuristics for Partitioning Sparse Matrices

Jiasen HUANG; Junyan REN; Wei LI

doi:10.1587/transinf.2015EDL8088

Greedy Approach Based Heuristics for Partitioning Sparse Matrices

Jiasen HUANG, Junyan REN, Wei LI

Full Text Views

0

Share
Cite this

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.

Publication: IEICE TRANSACTIONS on Information Vol.E98-D No.10 pp.1847-1851

Publication Date: 2015/10/01

Publicized: 2015/07/02

Online ISSN: 1745-1361

DOI: 10.1587/transinf.2015EDL8088

Type of Manuscript: LETTER

Category: Fundamentals of Information Systems

Authors

Jiasen HUANG
  Fudan University
Junyan REN
  Fudan University
Wei LI
  Fudan University

Keyword

partitioning, greedy approach, recursive merging, highest mean density, lowest average relative difference

Cite this

Copy

Jiasen HUANG, Junyan REN, Wei LI, "Greedy Approach Based Heuristics for Partitioning Sparse Matrices" in IEICE TRANSACTIONS on Information, vol. E98-D, no. 10, pp. 1847-1851, October 2015, doi: 10.1587/transinf.2015EDL8088.
Abstract: 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.
URL: https://globals.ieice.org/en_transactions/information/10.1587/transinf.2015EDL8088/_p

Copy

@ARTICLE{e98-d_10_1847,
author={Jiasen HUANG, Junyan REN, Wei LI, },
journal={IEICE TRANSACTIONS on Information},
title={Greedy Approach Based Heuristics for Partitioning Sparse Matrices},
year={2015},
volume={E98-D},
number={10},
pages={1847-1851},
abstract={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.},
keywords={},
doi={10.1587/transinf.2015EDL8088},
ISSN={1745-1361},
month={October},}

Copy

TY - JOUR
TI - Greedy Approach Based Heuristics for Partitioning Sparse Matrices
T2 - IEICE TRANSACTIONS on Information
SP - 1847
EP - 1851
AU - Jiasen HUANG
AU - Junyan REN
AU - Wei LI
PY - 2015
DO - 10.1587/transinf.2015EDL8088
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E98-D
IS - 10
JA - IEICE TRANSACTIONS on Information
Y1 - October 2015
AB - 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.
ER -