A Multilevel Algorithm for Wavefront Reduction
Authors:
- Y. F. HuYHY. F. Hu
- J. A. ScottJSJ. A. Scott
- 1 January 2001
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Scientific Computing
- Vol. 23 (4) , 1352-1375
Abstract
A multilevel algorithm for reordering sparse symmetric matrices to reduce the wavefront and profile is described. The algorithm is a combinatorial algorithm that uses a maximal independent vertex set for coarsening the adjacency graph of the matrix and an enhanced version of the Sloan algorithm on the coarsest graph. On a range of examples arising from practical applications, the multilevel algorithm is shown to produce orderings that are better than those produced by the Sloan algorithm and are of comparable quality to those obtained using the hybrid Sloan algorithm. Advantages over the hybrid Sloan algorithm are that the multilevel approach requires no spectral information and less CPU time.Keywords
This publication has 22 references indexed in Scilit:
- A multilevel unsymmetric matrix ordering algorithm for parallel process simulationComputers & Chemical Engineering, 2000
- An Analysis of Spectral Envelope Reduction via Quadratic Assignment ProblemsSIAM Journal on Matrix Analysis and Applications, 1997
- A spectral algorithm for envelope reduction of sparse matricesNumerical Linear Algebra with Applications, 1995
- Fast multilevel implementation of recursive spectral bisection for partitioning unstructured problemsConcurrency: Practice and Experience, 1994
- The use of profile reduction algorithms with a frontal codeInternational Journal for Numerical Methods in Engineering, 1989
- A comparasion of three resequencing algorithms for the reduction of matrix profile and wavefrontInternational Journal for Numerical Methods in Engineering, 1979
- Algorithm 509: A Hybrid Profile Reduction Algorithm [F1]ACM Transactions on Mathematical Software, 1976
- An Algorithm for Reducing the Bandwidth and Profile of a Sparse MatrixSIAM Journal on Numerical Analysis, 1976
- A property of eigenvectors of nonnegative symmetric matrices and its application to graph theoryCzechoslovak Mathematical Journal, 1975
- Algebraic connectivity of graphsCzechoslovak Mathematical Journal, 1973