The analysis of a nested dissection algorithm (Q1103322)

From MaRDI portal





scientific article; zbMATH DE number 4052881
Language Label Description Also known as
default for all languages
No label defined
    English
    The analysis of a nested dissection algorithm
    scientific article; zbMATH DE number 4052881

      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