NASA NTRS · 19950028509
A spectral algorithm for envelope reduction of sparse matrices
Abstract
A 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).
Keep this discovery
Explore connections, maps & timelines
Barnard, Stephen T., Pothen, Alex, Simon, Horst D.. 1993-11-01. A spectral algorithm for envelope reduction of sparse matrices. https://searchnasa.com/record/nasa%3A19950028509/a-spectral-algorithm-for-envelope-reduction-of-sparse-matrices
Citations retain the original authors and DOI and include this site’s record URL. If this discovery service contributed to your research, you can also cite Search NASA by Indiciae: BibTeX · RIS.