Loading...
Please wait, while we are loading the content...
Similar Documents
An analysis of spectral envelope-reduction via quadratic assignment problems
| Content Provider | NASA Technical Reports Server (NTRS) |
|---|---|
| Author | Pothen, Alex George, Alan |
| Copyright Year | 1994 |
| Description | A new spectral algorithm for reordering a sparse symmetric matrix to reduce its envelope size was described. 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 described 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 involved in an envelope Cholesky factorization scheme. We formulate the latter 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 projected quadratic assignment problem, and then show that finding a permutation matrix closest to an orthogonal matrix attaining one of the lower bounds justifies the spectral envelope reduction algorithm. The lower bound on the 2-sum is seen to be tight for reasonably 'uniform' finite element meshes. We also obtain asymptotically tight lower bounds for the envelope size for certain classes of meshes. |
| File Size | 1490730 |
| Page Count | 32 |
| File Format | |
| Alternate Webpage(s) | http://archive.org/details/NASA_NTRS_Archive_19950010181 |
| Archival Resource Key | ark:/13960/t82k1c70j |
| Language | English |
| Publisher Date | 1994-10-01 |
| Access Restriction | Open |
| Subject Keyword | Numerical Analysis Finite Element Method Permutations Algorithms Eigenvectors Spectra Laplace Transformation Graph Theory Computational Grids Orthogonality Cholesky Factorization Matrices Mathematics Symmetry Ntrs Nasa Technical Reports Server (ntrs) Nasa Technical Reports Server Aerodynamics Aircraft Aerospace Engineering Aerospace Aeronautic Space Science |
| Content Type | Text |
| Resource Type | Article |
