BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-77-645
       ENTRY:: June 28, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Generalized nested dissection
        TYPE:: Technical Report
      AUTHOR:: Lipton, Richard J.
      AUTHOR:: Rose, Donald J.
      AUTHOR:: Tarjan, Robert Endre
        DATE:: December 1977
       PAGES:: 34
    ABSTRACT:: 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) space and
               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.
       NOTES:: [Adminitrivia V1/Prg/19950628]
         END:: STAN//CS-TR-77-645