Abstract
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
Eigenvalues and eigenvectorsMathematicsAlgorithmMatrix (chemical analysis)Permutation matrixEnvelope (radar)Reduction (mathematics)SortingLaplacian matrixRelaxation (psychology)Sparse matrixLaplace operatorCirculant matrixComputer scienceGaussianMathematical analysisGeometry
Affiliated Institutions
Related Publications
Partitioning Sparse Matrices with Eigenvectors of Graphs
The problem of computing a small vertex separator in a graph arises in the context of computing a good ordering for the parallel factorization of sparse, symmetric matrices. An ...
On the Quality of Spectral Separators
Computing graph separators is an important step in many graph algorithms. A popular technique for finding separators involves spectral methods. However, there has not been much ...
New spectral methods for ratio cut partitioning and clustering
Partitioning of circuit netlists in VLSI design is considered. It is shown that the second smallest eigenvalue of a matrix derived from the netlist gives a provably good approxi...
Kernel k-means
Kernel k-means and spectral clustering have both been used to identify clusters that are non-linearly separable in input space. Despite significant research, these methods have ...
Co-clustering documents and words using bipartite spectral graph partitioning
Both document clustering and word clustering are well studied problems. Most existing algorithms cluster documents and words separately but not simultaneously. In this paper we ...
Publication Info
- Year
- 1995
- Type
- article
- Volume
- 2
- Issue
- 4
- Pages
- 317-334
- Citations
- 156
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
156
OpenAlex
Cite This
Stephen T. Barnard,
Alex Pothen,
Horst D. Simon
(1995).
A spectral algorithm for envelope reduction of sparse matrices.
Numerical Linear Algebra with Applications
, 2
(4)
, 317-334.
https://doi.org/10.1002/nla.1680020402
Identifiers
- DOI
- 10.1002/nla.1680020402