An Analysis of Spectral Envelope Reduction via Quadratic Assignment Problems
Authors:
- Alan GeorgeAGAlan George
- Alex PothenAPAlex Pothen
- 1 July 1997
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Matrix Analysis and Applications
- Vol. 18 (3) , 706-732
Abstract
A new spectral algorithm for reordering a sparse symmetric matrix to reduce its envelope size was described in [Barnard, Pothen, and Simon, Numer. Linear Algebra Appl., 2 (1995), pp. 317--334]. The ordering is computed by associating a Laplacian matrix with the given matrix and then sorting the components of a specified eigenvector of the Laplacian. In this paper we provide an analysis of the spectral envelope reduction algorithm. We describe related 1- and 2-sum problems; the former is related to the envelope size, while the latter is related to an upper bound on the work in an envelope Cholesky factorization. We formulate these two problems as quadratic assignment problems and then study the 2-sum problem in more detail. We obtain lower bounds on the 2-sum by considering a relaxation of the problem and then show that the spectral ordering finds a permutation matrix closest to an orthogonal matrix attaining the lower bound. This provides a stronger justification of the spectral envelope reduction algorit...Keywords
This publication has 30 references indexed in Scilit:
- Two graph algorithms derivedActa Informatica, 1999
- A spectral algorithm for envelope reduction of sparse matricesNumerical Linear Algebra with Applications, 1995
- Ordering Methods for Preconditioned Conjugate Gradient Methods Applied to Unstructured Grid ProblemsSIAM Journal on Matrix Analysis and Applications, 1992
- The effect of ordering on preconditioned conjugate gradientsBIT Numerical Mathematics, 1989
- The use of profile reduction algorithms with a frontal codeInternational Journal for Numerical Methods in Engineering, 1989
- λ1, Isoperimetric inequalities for graphs, and superconcentratorsJournal of Combinatorial Theory, Series B, 1985
- 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