Calculs de complexité relatifs à une méthode de dissection emboîtée. (French) Zbl 0537.65025

A ”nested dissection” ordering is given for solving any system of linear equations \(A\cdot X=B\) for the family of sparse symmetric positive definite matrices corresponding to the class of graphs of bounded degree whose subgraphs satisfy a \(\sqrt{n}\)-separator theorem, and we prove O(n.log(n)) fill and \(O(n\sqrt{n})\) operation count bounds. Then, the general implementation scheme in the finite element package MODULEF, for two-dimensional finite element problems, is presented, and some numerical results are given.


65F05 Direct numerical methods for linear systems and matrix inversion
65F50 Computational methods for sparse matrices
65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs


Full Text: DOI EuDML


[1] Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The design and analysis of computer algorithms. Reading, Ma: Addison Wesly 1974 · Zbl 0326.68005
[2] Berge, C.: Graphes et hypergraphes, 2e édition. Paris: Dunod 1973 · Zbl 0332.05101
[3] Ciarlet, P.G.: Numerical analysis of the finite element method. Séminaire de Mathématiques Supérieures, Presses de l’Université de Montréal: 1976
[4] George, J.A.: Nested Dissection of a regular finite element mesh. SIAM J. Numer. Anal.10, 345-367 (1973) · Zbl 0259.65087 · doi:10.1137/0710032
[5] George, J.A., Liu, J.W.-H.: Computer solution of large sparse positive definite systems. Englewood Cliffs, New Jersey: Prentice Hall 1981 · Zbl 0516.65010
[6] Gibbs, N.E., Poole, W.G., Jr., Stockmeyer, P.: An algorithm for reducing the bandwidth and profile of a sparse matrix. SIAM J. Numer. Anal.13, 236-251 (1976) · Zbl 0329.65024 · doi:10.1137/0713023
[7] Gilbert, J.R.: Graph separator theorems and sparse Gaussian elimination. Technical report STAN-CS-80-833, Computer Science Department, Stanford University (1980)
[8] 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
[9] 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
[10] Marro, L.: Méthodes de réduction de la largeur de bande et du profil efficace des matrices creuses. Thèse de 3e cycle, Université de Nice (1980)
[11] Parter, S.: The use of linear graphs in Gauss elimination. SIAM Rev.3, 119-130 (1961) · Zbl 0102.11302 · doi:10.1137/1003021
[12] Perronnet, A., Begis, D.: Présentation du Club MODULEF. Version 3.4, Modulef-85, INRIA 1983 · Zbl 0566.65077
[13] Roman, J.: Sur la renumérotation des noeuds d’interpolation d’un maillage plan d’éléments finis à l’aide de l’algorithme de séparation de LIPTON et TARJAN. Thèse de 3ème cycle, U.E.R. de Mathématiques et d’Informatique, Université de Bordeaux I (1980)
[14] Roman, J.: Calculs de complexité relatifs à une méthode de dissection emboîtée. Rapport technique n{\(\deg\)} 8303, U.E.R. de Mathématiques et d’Informatique, Université de Bordeaux I (1983)
[15] Roman, J.: Implémentation dans MODULEF de l’algorithme de séparation pour les graphes planaires de LIPTON-TARJAN: application à la numérotation dans des problèmes plans d’éléments finis. Comptes rendus du troisième Congrès International sur les méthodes numériques de l’ingénieur, GAMNI-ISINA-AFCET. P. Lascaux ed. Paris: Pluralis (14-16 Mars, 1983)
[16] Rose, D.J.: A Graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations. Graph Theory Comput. R.C. Read (ed.), pp. 183-217. New York: Academic Press 1973
[17] 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
[18] Wikinson, J.H.: The algebraic eigenvalue problem. London, New York: Oxford University Press 1965
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.