1979/04/01 by Richard J. Lipton, Donald J. Rose, Robert E. Tarjan · 562 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Interconnection Networks and Systems #Complexity and Algorithms in Graphs #Mathematics #Gaussian elimination #Combinatorics #Planar #Planar graph #Gaussian #Finite element method #Discrete mathematics #System of linear equations #Graph #Applied mathematics #Mathematical analysis #Computer science
paper · doi:10.1137/0716027
published in SIAM Journal on Numerical Analysis 16(2), 346-358 (Society for Industrial and Applied Mathematics)
openalex publication_date 1979/04/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/08
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(nlog 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.