The analysis of a nested dissection algorithm (Q1103322)

From MaRDI portal
Revision as of 08:26, 30 July 2024 by Openalex240730090724 (talk | contribs) (Set OpenAlex properties.)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
The analysis of a nested dissection algorithm
scientific article

    Statements

    The analysis of a nested dissection algorithm (English)
    0 references
    0 references
    0 references
    1987
    0 references
    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.
    0 references
    sparsity preservation
    0 references
    sparse-contractible graph
    0 references
    topological graph theory
    0 references
    nested dissection algorithm
    0 references
    Gauss elimination
    0 references
    symmetric positive definite matrices
    0 references
    separators in planar graphs
    0 references
    George-Liu algorithm
    0 references
    finite element graphs
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references