The analysis of a nested dissection algorithm (Q1103322): Difference between revisions

The nested dissection algorithm invented by \textit{A. George} [SIAM J. Numer. Anal. 10, 345-363 (1973; Zbl 0259.65087)] is for preserving the sparsity in Gauss elimination on symmetric positive definite matrices. In the original algorithm by \textit{A. George} and \textit{J. W.-H. Liu} [ibid. 15, 1053-1070 (1978; Zbl 0408.65064)], a heuristic for finding separators is used. \textit{R. E. Lipton} and the second author [SIAM J. Appl. Math. 36, 177-189 (1979; Zbl 0432.05022)] gave an algorithm for finding separators in planar graphs and two-dimensional finite element graphs; \textit{R. J. Lipton}, \textit{D. J. Rose} and the second author [SIAM J. Numer. Anal. 16, 346-358 (1979; Zbl 0435.65021)] used these separators in a modified version of nested dissection (with bounds O(n log n) of fill and \(O(n^{3/2})\) on operation count.) This paper is analyzing the combination of the original George-Liu algorithm and the Lipton-Tarjan planar separator algorithm. This combination can be implemented in an easier way than the Lipton-Rose- Tarjan version. Based on some topological graph theory, bounds O(n log n) of fill and \(O(n^{3/2})\) on operation count are proved for planar graphs, two dimensional finite element graphs, graphs of bounded degree with \(n^{1/2}\)-separators.