Generalized Nested Dissection

J. A. George has discovered a method, called nested dissection, for solving a system of linear equations defined on an n = k k square grid in O (n 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.