IEICE TRANSACTIONS on Information
Greedy Approach Based Heuristics for Partitioning Sparse Matrices
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
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
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://global.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 -
English
