The analysis of a nested dissection algorithm

John R. Gilbert, Robert Endre Tarjan

Research output: Contribution to journalArticlepeer-review

69 Scopus citations

Abstract

Nested dissection is an algorithm invented by Alan George for preserving sparsity in Gaussian elimination on symmetric positive definite matrices. Nested dissection can be viewed as a recursive divide-and-conquer algorithm on an undirected graph; it uses separators in the graph, which are small sets of vertices whose removal divides the graph approximately in half. George and Liu gave an implementation of nested dissection that used a heuristic to find separators. Lipton and Tarjan gave an algorithm to find n1/2-separators in planar graphs and two-dimensional finite element graphs, and Lipton, Rose, and Tarjan used these separators in a modified version of nested dissection, guaranteeing bounds of O (n log n) on fill and O(n3/2) on operation count. We analyze the combination of the original George-Liu nested dissection algorithm and the Lipton-Tarjan planar separator algorithm. This combination is interesting because it is easier to implement than the Lipton-Rose-Tarjan version, especially in the framework of existïng sparse matrix software. Using some topological graph theory, we prove O(n log n) fill and O(n3/2) operation count bounds for planar graphs, twodimensional finite element graphs, graphs of bounded genus, and graphs of bounded degree with n1/2-separators. For planar and finite element graphs, the leading constant factor is smaller than that in the Lipton-Rose-Tarjan analysis. We also construct a class of graphs with n1/2-separators for which our algorithm does not achieve an O(n log n) bound on fill.

Original languageEnglish (US)
Pages (from-to)377-404
Number of pages28
JournalNumerische Mathematik
Volume50
Issue number4
DOIs
StatePublished - Jul 1 1986

All Science Journal Classification (ASJC) codes

  • Computational Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'The analysis of a nested dissection algorithm'. Together they form a unique fingerprint.

Cite this