Title :
A spectral algorithm for envelope reduction of sparse matrices
Author :
Barnard, Stephen T. ; Pothen, Alex ; Simon, Horst D.
Author_Institution :
Cray Res. Inc., Moffett Field, CA, USA
Abstract :
An 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 or SPARSPAK´s reverse Cuthill-McKee.
Keywords :
eigenvalues and eigenfunctions; graph theory; numerical analysis; parallel algorithms; sparse matrices; Gibbs-Poole-Stockmeyer algorithm; Laplacian matrix; SPARSPAK reverse Cuthill-McKee algorithm; eigenvector; eigenvectors; envelope reduction; graph; numerical values; parallel algorithms; reordering algorithm; sparse matrices; spectral algorithm; Computer science; Eigenvalues and eigenfunctions; Global Positioning System; Iterative algorithms; Iterative methods; Laplace equations; Linear systems; NASA; Sparse matrices; Symmetric matrices;
Conference_Titel :
Supercomputing '93. Proceedings
Print_ISBN :
0-8186-4340-4
DOI :
10.1109/SUPERC.1993.1263497
