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

fYear

1993

fDate

15-19 Nov. 1993

Firstpage

493

Lastpage

502

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;

fLanguage

English

Publisher

ieee

Conference_Titel

Supercomputing '93. Proceedings

ISSN

1063-9535

Print_ISBN

0-8186-4340-4

Type

conf

DOI

10.1109/SUPERC.1993.1263497

Filename

1263497