Accession Number:

ADA113104

Title:

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

Descriptive Note:

Technical rept.,

Corporate Author:

BOEING COMPUTER SERVICES CO TUKWILA WA

Personal Author(s):

Report Date:

1982-01-01

Pagination or Media Count:

20.0

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

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE