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

摘要

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)