Generalized Nested Dissection
Richard J. Lipton, Donald J. Rose, Robert Endre Tarjan · SIAM Journal on Numerical Analysis · 1979
J. A. George has discovered a method, called nested dissection, for solving a system of linear equations defined on an $n = k \times k$ square grid in $O(n\log n)$ and space $O(n^{{3 /2}} )$ time. We generalize this method without degrading the time and space bounds so that it applies to any system of equations defined on a planar or almost-planar graph. Such systems arise in the solution of two-dimensional finite element problems. Our method uses the fact that planar graphs have good separators. More generally, we show that sparse Gaussian elimination is efficient for any class of graphs which have good separators, and conversely that graphs without good separators (including “almost all” sparse graphs) are not amenable to sparse Gaussian elimination.
Cited by 560 works. doi:10.1137/0716027
Authors
References
- The Design and Analysis of Computer Algorithms
- The finite element method in engineering science
- Gaussian elimination is not optimal
- Probabilistic Methods in Combinatorics
- Computer Solution of Linear Algebraic Systems
- Algorithmic Aspects of Vertex Elimination on Graphs
- A Separator Theorem for Planar Graphs
- Efficient Algorithms for Shortest Paths in Sparse Networks
- Nested Dissection of a Regular Finite Element Mesh
- A GRAPH-THEORETIC STUDY OF THE NUMERICAL SOLUTION OF SPARSE POSITIVE DEFINITE SYSTEMS OF LINEAR EQUATIONS