Accession Number : ADA113104

Title :   Implementation of the Gibbs-Poole-Stockmeyer Algorithm and the Gibbs-King Algorithm.

Descriptive Note : Technical rept.,


Personal Author(s) : Lewis,John Gregg

PDF Url : ADA113104

Report Date : Jan 1982

Pagination or Media Count : 20

Abstract : Implementations of two effective matrix reordering algorithms were published in this paper as Algorithms 508, which implements the Gibbs-Poole-Stockmeyer algorithm for reducing the bandwidth of a matrix, and 509, which implements the Gibbs-King algorithm for reducing the profile of a matrix. Reduction of matrix profile is more often required than bandwidth reduction, but Algorithm 509 is substantially slower than Algorithm 508. Consequently, the Gibbs-Poole-Stockmeyer algorithm has been recommended and used in contexts where the better profile reduction provided by the Gibbs-King algorithm would be more appropriate. In addition, Algorithms 508 and 509 both contain unnecessary restrictions on problem size and provide little error checking. The authors describe a new FORTRAN implementation of both reordering algorithms which is portable, faster, more reliable and uses less storage than the original implementations. The new implementation of the Gibbs-King algorithm is much faster than Algorithm 509, generally slightly faster than Algorithm 508 and nearly as fast as the new implementation of the Gibbs-King-Stockmeyer algorithm. (Author)

Descriptors :   *Matrix theory, *Sparse matrix, Matrices(Mathematics), Algorithms, Reduction, Bandwidth, Wavefronts, Sizes(Dimensions), Errors, Profiles, FORTRAN, Coefficients, Symmetry, Heuristic methods

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE