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

Roman, J.

Numer. Math. 47, 175-190 (1985).

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.

MSC:

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

Keywords:

finite element method; sparse matrix; Gaussian elimination; nested dissection; separator; planar graph; numerical results

Software:

symrcm

References:

[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
[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
[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
[9]	Lipton, R.J., Rose, D.J., Tarjan, R.E.: Generalized nested dissection. SIAM J. Numer. Anal.16, 346-358 (1979) · Zbl 0435.65021
[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
[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
[18]	Wikinson, J.H.: The algebraic eigenvalue problem. London, New York: Oxford University Press 1965