Algorithm 582: The Gibbs-Poole-Stockmeyer and Gibbs-King Algorithms for Reordering Sparse Matrices

Given the structure of a symmetric or structurally s y m m e t r i c sparse matrix, G P S K C A a t t e m p t s to find a synlnaetric reordering of the matrix that produces a smaller bandwidth or profile.References [1], [4], [5], and [6] explain in detail the algorithms realized by G P S K C A .This algorithm provides the same m a t h e m a t i c a l capabilities as provided by R E D U C E , Algorithms 508, and 509, but requires less m e m o r y and time and removes some implicit restrictions on the matrices t h a t can be reordered.A description of the differences in the implementation and their effects is given in [7]; G P S K C A and R E D U C E produce the same bandwidth and profile on all problems for which R E D U C E executes successfully.T h e package of subroutines is evoked by the F O R T R A N s t a t e m e n t CALL GPSKCA (N, NZ, CONNEC, RSTART, DEGREE, OPTPRO, PERMUT, WORK, WRKLEN, ERROR, SPACE)where the p a r a m e t e r s are described in the listing given here.T h e subroutines a t t e m p t ' t o find a symmetric (row and column) p e r m u t a t i o n t h a t reduces the bandwidth or profile of the reordered matrix.W h e t h e r to emphasize profile reduction or bandwidth reduction is determined by the logical p a r a m e t e r O P T -PRO.A c o m m o n use for this algorithm will be prior to the solution of sparse linear algebraic equations or algebraic eigenvalue problems of moderately large size.