A spectral algorithm for envelope reduction of sparse matrices
Authors:
- 1 July 1995
- journal article
- research article
- Published by Wiley in Numerical Linear Algebra with Applications
- Vol. 2 (4) , 317-334
Abstract
The problem of reordering a sparse symmetric matrix to reduce its envelope size is considered. A new spectral algorithm for computing an envelope‐reducing reordering is obtained by associating a Laplacian matrix with the given matrix and then sorting the components of a specified eigenvector of the Laplacian. This Laplacian eigenvector solves a continuous relaxation of a discrete problem related to envelope minimization called the minimum 2‐sum problem. The permutation vector computed by the spectral algorithm is a closest permutation vector to the specified Laplacian eigenvector. Numerical results show that the new reording algorithm usually computes smaller envelope sizes than those obtained from the current standards such as the Gibbs—Poole—Stockmeyer (GPS) algorithm or the reverse Cuthill—McKee (RCM) algorithm in SPARSPAK, in some cases reducing the envelope by more than a factor of two.Keywords
This publication has 17 references indexed in Scilit:
- Fast multilevel implementation of recursive spectral bisection for partitioning unstructured problemsConcurrency: Practice and Experience, 1994
- Optimal linear labelings and eigenvalues of graphsDiscrete Applied Mathematics, 1992
- Partitioning of unstructured problems for parallel processingComputing Systems in Engineering, 1991
- Partitioning Sparse Matrices with Eigenvectors of GraphsSIAM Journal on Matrix Analysis and Applications, 1990
- A New Algorithm for Finding a Pseudoperipheral Node in a GraphSIAM Journal on Matrix Analysis and Applications, 1990
- The effect of ordering on preconditioned conjugate gradientsBIT Numerical Mathematics, 1989
- Vectorization of a Multiprocessor Multifrontal CodeThe International Journal of Supercomputing Applications, 1989
- Progress in Sparse Matrix Methods for Large Linear Systems On Vector SupercomputersThe International Journal of Supercomputing Applications, 1987
- Implementation of the Gibbs-Poole-Stockmeyer and Gibbs-King AlgorithmsACM Transactions on Mathematical Software, 1982
- Algorithm 509: A Hybrid Profile Reduction Algorithm [F1]ACM Transactions on Mathematical Software, 1976