Open AccessParallel Implementations of RCM Algorithm for Bandwidth Reduction of Sparse Matrices
Author(s) -
Thiago Nascimento Rodrigues,
Maria Claudia Silva Bóeres,
Lúcia Catabriga
Publication year - 2018
Publication title -
tema
Language(s) - English
Resource type - Journals
eISSN - 2179-8451
pISSN - 1677-1966
DOI - 10.5540/tema.2017.018.03.449
Subject(s) - computer science , sparse matrix , parallel computing , algorithm , computation , implementation , parallel algorithm , reduction (mathematics) , bandwidth (computing) , mathematics , computer network , geometry , physics , quantum mechanics , gaussian , programming language
The Reverse Cuthill-McKee (RCM) algorithm is a well-known heuristicfor reordering sparse matrices. It is typically used to speed up the computation ofsparse linear systems of equations. This paper describes two parallel approachesfor the RCM algorithm as well as an optimized version of each one based on someproposed enhancements. The first one exploits a strategy for reducing lazy threads,while the second one makes use of a static bucket array as the main data structureand suppress some steps performed by the original algorithm. These related changesled to outstanding reordering time results and significant bandwidth reductions.The performance of two algorithms is compared with the respective implementationmade available by Boost library. The OpenMP framework is used for supportingthe parallelism and both versions of the algorithm are tested with large sparse andstructural symmetric matrices.