Catalog Home Page

Algorithms for the reduction of matrix bandwidth and profile

Smyth, W.F. (1985) Algorithms for the reduction of matrix bandwidth and profile. Journal of Computational and Applied Mathematics, 12-13 . pp. 551-561.

Link to Published Version: http://dx.doi.org/10.1016/0377-0427(85)90048-2
*Subscription may be required

Abstract

Since 1969 a standard approach to the reduction of matrix bandwidth and profile has been to grow rooted level structures (RLSs) of the adjacency graph of the matrix, and then to use the ‘best’ RLS to generate a renumbering of the rows and columns. A generally effective, low-cost method for RLS growth is the Gibbs-Poole-Stockmeyer (GPS) algorithm, especially as modified by George and Liu. Recent work by Arany has suggested alternatives to the GPS algorithm. In this paper, algorithms proposed by Arany and several other new algorithms are described, and results of preliminary computer tests on ‘difficult’ renumbering problems are presented. In particular, RLSF width, bandwidth, profile, and CPU time are compared for four algorithms: Minimum Degree GPS, Minimum Degree Arany, Minimum Width Arany, and Maximum Swing.

Publication Type: Journal Article
Publisher: Elsevier BV
Copyright: © 1985 Published by Elsevier B.V.
URI: http://researchrepository.murdoch.edu.au/id/eprint/27385
Item Control Page Item Control Page