Name
Abstract | ||
|---|---|---|
The authors describe the novel spectral nested dissection (SND) algorithm, a novel algorithm for computing orderings appropriate for parallel factorization of sparse, symmetric matrices. The algorithm makes use of spectral properties of the Laplacian matrix associated with the given matrix to compute separators. The authors evaluate the quality of the spectral orderings with respect to several measures: fill, elimination tree height, height and weight balances of elimination trees, and clique tree heights. They use some very large structural analysis problems as test cases and demonstrate on these real applications that spectral orderings compare quite favorably with commonly used orderings, outperforming them by a wide margin for some of these measures. The only disadvantage of SND is its relatively long execution time |
Year | DOI | Venue |
|---|---|---|
1992 | 10.1109/SUPERC.1992.236711 | Minneapolis, MN |
Keywords | Field | DocType |
matrix algebra,parallel algorithms,C ray Y-MP,Laplacian matrix,clique tree heights,elimination tree height,elimination trees,execution time,fill,height and weight balances,parallel factorization,separators,sparce matrices,spectral nested dissection,spectral properties,structural analysis problems,symmetric matrices | Graph theory,Laplacian matrix,Parallel algorithm,Computer science,Matrix (mathematics),Parallel computing,Nested dissection,Symmetric matrix,Factorization,Eigenvalues and eigenvectors | Conference |
ISBN | Citations | PageRank |
978-0-8186-2630-2 | 28 | 8.17 |
References | Authors | |
6 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pothen, A. | 1 | 28 | 8.17 |
| Horst D. Simon | 2 | 1900 | 263.98 |
| Wang, L. | 3 | 139 | 13.98 |
| Barnard, S.T. | 4 | 28 | 8.17 |