A spectral algorithm for envelope reduction of sparse matricesA new algorithm for reducing the envelope of a sparse matrix is presented. This algorithm is based on the computation of eigenvectors of the Laplacian matrix associated with the graph of the sparse matrix. A reordering of the sparse matrix is determined based on the numerical values of the entries of an eigenvector of the Laplacian matrix. Numerical results show that the new reordering algorithm can in some cases reduce the envelope by more than a factor of two over the current standard algorithms such as Gibbs-Poole-Stockmeyer (GPS) or SPARSPAK's reverse Cuthill-McKee (RCM).
Document ID
19950028509
Acquisition Source
Legacy CDMS
Document Type
Conference Paper
Authors
Barnard, Stephen T. (Cray Research, Inc. Moffett Field, CA, United States)
Pothen, Alex (Waterloo Univ. Ontario, Canada)
Simon, Horst D. (Computer Sciences Corp. Moffett Field, CA, United States)