An Automatic Nested Dissection Algorithm for Irregular Finite Element Problems
Alan D. George, Joseph W. H. Liu · SIAM Journal on Numerical Analysis · 1978
A formal definition of a nested dissection ordering of the graph of a general sparse symmetric matrix A is given. After introducing some preliminary results which provide a direct relationship between the structures of A and its triangular factor L, where $A = LL^T $, some results about fill for nested dissection orderings are provided. Finally, a heuristic algorithm is described for finding a nested dissection ordering for an undirected graph, along with appropriate data structures and a storage allocation scheme for a linear equation solver to use such orderings. The ordering algorithm/linear equation solver combination is applied to the graphs of matrices arising in typical finite element applications, and numerical experiments are provided which indicate that our combination of ordering and solution schemes is superior to standard band or envelope schemes as long as the problems are moderately large.
Cited by 158 works. doi:10.1137/0715069
Authors
References
- The Design and Analysis of Computer Algorithms
- The finite element method in engineering science
- An analysis of the finite element method
- The Theory of Graphs and Its Applications
- Algorithmic Aspects of Vertex Elimination on Graphs
- A Separator Theorem for Planar Graphs
- Nested Dissection of a Regular Finite Element Mesh
- Reducing the bandwidth of sparse symmetric matrices
- A GRAPH-THEORETIC STUDY OF THE NUMERICAL SOLUTION OF SPARSE POSITIVE DEFINITE SYSTEMS OF LINEAR EQUATIONS
- The Use of Linear Graphs in Gauss Elimination