The analysis of a nested dissection algorithm. (English) Zbl 0645.65012

The nested dissection algorithm invented by 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 A. George and J. W.-H. Liu [ibid. 15, 1053-1070 (1978; Zbl 0408.65064)], a heuristic for finding separators is used. 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; R. J. Lipton, 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.
Reviewer: I.Arany


65F05 Direct numerical methods for linear systems and matrix inversion
65F50 Computational methods for sparse matrices
05C10 Planar graphs; geometric and topological aspects of graph theory


Full Text: DOI EuDML


[1] Djidjev, H.N.: On the problem of partitioning planar graphs. SIAM J. Algebraic Discrete Methods3, 229-240 (1982) · Zbl 0503.05057 · doi:10.1137/0603022
[2] George, A.: Nested dissection of a regular finite element mesh. SIAM J. Numer. Anal.10, 345-363 (1973) · Zbl 0259.65087 · doi:10.1137/0710032
[3] George, A., Liu, J.W.-H.: An automatic neste dissection algorithm for irregular finite element problems. SIAM J. Numer. Anal.15, 1053-1069 (1978) · Zbl 0408.65064 · doi:10.1137/0715069
[4] George, A., Liu, J.W.-H.: Computer Solution of Large Sparse Positive Definite Systems. Englewood Cliffs, NJ: Prentice-Hall 1981 · Zbl 0516.65010
[5] Gilbert, J.R.: Graph Separator Theorems and Sparse Gaussian Elimination. Ph.D. thesis, Stanford University 1980
[6] Gilbert, J.R., Hutchinson, J.P., Tarjan, R.E.: A separator theorem for graphs of bounded genus. J. Algorithms5, 391-407 (1984) · Zbl 0556.05022 · doi:10.1016/0196-6774(84)90019-1
[7] Gilbert, J.R., Rose, D.J., Edenbrandt, A.: A separator theorem for chordal graphs. SIAM J. Algebraic Discrete Methods5, 306-313 (1984) · Zbl 0551.05049 · doi:10.1137/0605032
[8] Gilbert, J.R., Schreiber, R.: Nested dissection with partial pivoting. Sparse Matrix Symposium. Fairfield Glade, Tennessee 1982
[9] Harary, F.: Graph Theory. Reading, MA: Addison-Wesley 1969 · Zbl 0182.57702
[10] Hoey, D., Leiserson, C.E.: A layout for the shuffle-exchange network. Carnegie-Mellon University Computer Science Department technical report CMU-CS-80-139 (1980)
[11] Jordan, C.: Sur les assemblages de lignes. J. Reine Angew. Math.70, 185-190 (1869) · doi:10.1515/crll.1869.70.185
[12] Leighton, F.T.: A layout strategy for VLSI which is provably good. Proc. 14th Ann. ACM Symp. Theory Comput. pp. 85-98 (1982)
[13] Leiserson, C.E.: Area-efficient graph layouts (for VLSI). Proc. 21st Ann. Symp. Found. Comput. Sci. pp. 270-281 (1980)
[14] Lipton, R.J., Rose, D.J., Tarjan, R.E.: Generalized nested dissection. SIAM J. Numer. Anal.16, 346-358 (1979) · Zbl 0435.65021 · doi:10.1137/0716027
[15] Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Appl. Math.36, 177-189 (1979) · Zbl 0432.05022 · doi:10.1137/0136016
[16] Miller, G.L.: Finding small simple cycle separators for 2-connected planar graphs. Proc. 16th Ann. ACM Symp. Theory Comput. pp. 376-382 (1984)
[17] Nash-Williams, C.St.J.A.: Decomposition of finite graphs into forests. J. Lond. Math. Soc.39, 12 (1964) · Zbl 0119.38805 · doi:10.1112/jlms/s1-39.1.12
[18] Parter, S.: The use of linear graphs in Gauss elimination. SIAM Rev.3, 119-130 (1961) · Zbl 0102.11302 · doi:10.1137/1003021
[19] Roman, J.: Calculs de complexit? relatifs ? une m?thode de dissection embo?t?e. Numer. Math.47, 175-190 (1985) · doi:10.1007/BF01389708
[20] Rose, D.J.: A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations. In: Graph Theory and Computing (R.C. Read, ed.), pp. 183-217. New York: Academic Press 1972 · Zbl 0266.65028
[21] Rose, D.J., Tarjan, R.E., Lueker, G.S.: Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput.5, 266-283 (1976) · Zbl 0353.65019 · doi:10.1137/0205021
[22] Yannakakis, M.: Computing the minimum fill-in is NP-complete. SIAM J. Algebraic Discrete Methods2, 77-79 (1981) · Zbl 0496.68033 · doi:10.1137/0602010
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.