Loading...
Please wait, while we are loading the content...
Similar Documents
A spectral algorithm for envelope reduction of sparse matrices
| Content Provider | NASA Technical Reports Server (NTRS) |
|---|---|
| Author | Simon, Horst D. Pothen, Alex Barnard, Stephen T. |
| Copyright Year | 1993 |
| Description | 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 reordering algorithm usually computes smaller envelope sizes than those obtained from the current standard algorithms such as Gibbs-Poole-Stockmeyer (GPS) or SPARSPAK reverse Cuthill-McKee (RCM), in some cases reducing the envelope by more than a factor of two. |
| File Size | 1062378 |
| Page Count | 40 |
| File Format | |
| Alternate Webpage(s) | http://archive.org/details/NASA_NTRS_Archive_19970009822 |
| Archival Resource Key | ark:/13960/t3615z967 |
| Language | English |
| Publisher Date | 1993-10-01 |
| Access Restriction | Open |
| Subject Keyword | Computer Programming And Software Permutations Algorithms Eigenvectors Spectra Matrix Theory Parallel Processing Computers Matrices Mathematics Ntrs Nasa Technical Reports Server (ntrs) Nasa Technical Reports Server Aerodynamics Aircraft Aerospace Engineering Aerospace Aeronautic Space Science |
| Content Type | Text |
| Resource Type | Technical Report |
