Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

Learn more

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:
*Subscription may be required


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.

Item Type: Journal Article
Publisher: Elsevier BV
Copyright: © 1985 Published by Elsevier B.V.
Item Control Page Item Control Page