## 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 n^{1/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(n^{3/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(n^{3/2}) operation count bounds for planar graphs, twodimensional finite element graphs, graphs of bounded genus, and graphs of bounded degree with n^{1/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 n^{1/2}-separators for which our algorithm does not achieve an O(n log n) bound on fill.

Original language | English (US) |
---|---|

Pages (from-to) | 377-404 |

Number of pages | 28 |

Journal | Numerische Mathematik |

Volume | 50 |

Issue number | 4 |

DOIs | |

State | Published - Jul 1986 |

## All Science Journal Classification (ASJC) codes

- Computational Mathematics
- Applied Mathematics

## Keywords

- Subject Classifications: AMS(MOS), 05C10, 65F05, 65F50, CR, G.1.3, G.2.2