Algorithms for the reduction of matrix bandwidth and profile

摘要

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.