A constructive bandwidth reduction algorithm—A variant of GPS algorithm

Abstract

In this paper, a new viable bandwidth reduction algorithm for reducing the bandwidth of sparse symmetric matrices, is described. The proposed algorithm provides a reliable procedure to reduce the bandwidth and can easily be applied to the sparse symmetric matrices of any size. This algorithm is tested on structured graphs and the reduced bandwidth results obtained are compared with the GPS algorithm. The bandwidth obtained by the present method is smaller than or equal to the one obtained by the GPS and standard examples are included to illustrate in detail the proposed algorithm.

Keywords

• Bandwidth reduction
• Sparse symmetric matrix
• GPS algorithm
• Reordering of graph vertices
• BFS algorithm