Algorithmique et calculs de complexité pour un solveur de type dissections emboîtées. (Algorithmic study and complexity bounds for a nested dissection solver). (French) Zbl 0663.65020

Charrier, P.; Roman, J.

Numer. Math. 55, No. 4, 463-476 (1989).

We consider the nested dissection method based on separator theorems introduced by R. E. Tarjan [ibid. 50, 377-404 (1987; Zbl 0645.65012)] and the second author [ibid. 47, 175-190 (1985; Zbl 0537.65025)] used for solving large sparse systems of linear equations. More precisely, we study a block storage scheme such as proposed by A. George [SIAM J. Numer. Anal. 14, 161-179 (1977; Zbl 0356.65023)] for regular square grids and we prove the following results: first, for families of graphs of bounded degree with \(n^{\sigma}\)-separator theorem, \(1/2\leq \sigma <1\), the overhead storage of the block data structure for the factored matrix is linear in system dimension; on the other hand, by adding a non restrictive assumption on the separation, this structure can be constructed by a block symbolic factorization which runs in time linear in matrix dimension. Numerical experiments illustrating these theoretical results are provided.

Reviewer: P.Charrier

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:

Gauss elimination; separator theorem; complexity; nested dissection method; large sparse systems; block storage scheme; Numerical experiments

Citations:

Zbl 0645.65012; Zbl 0537.65025; Zbl 0356.65023

Software:

symrcm

References:

[1]	Charrier, P., Roman, J.: Algorithmique et calculs de complexité pour un solveur de type dissections emboîtées. Rapport interne Informatique, Université de Bordeaux 1 1986
[2]	George, J.A.: Nested dissection of a regular finite element mesh. SIAM J. Numer. Anal.10, 345?367 (1973) · Zbl 0259.65087
[3]	George, J.A.: Numerical experiments using dissection methods to solven byn grid problems. SIAM J. Numer. Anal.14, 161?179 (1977) · Zbl 0356.65023
[4]	George, J.A., Liu, J.W.H.: An automatic nested dissection algorithm for irregular finite element problems. SIAM J. Numer. Anal.15, 1053?1069 (1978) · Zbl 0408.65064
[5]	George, J.A., Liu, J.W.H.: Algorithms for matrix partioning and the numerical solution of finite element systems. SIAM J. Numer. Anal.15, 297?327 (1978) · Zbl 0389.65015
[6]	George, J.A., Liu, J.W.H.: An optimal algorithm for symbolic factorization of symmetric matrices. SIAM J. Comput.9, 583?593 (1980) · Zbl 0452.68049
[7]	George, J.A., Liu, J.W.H.: Computer solution of large sparse positive definite systems, Ed. Englewood Cliffs, New Jersey: Prentice Hall 1981 · Zbl 0516.65010
[8]	George, J.A., Poole, W.G. Jr., Voigt, R.G.: Incomplete nested dissection for solvingn byn grid problems. SIAM J. Numer. Anal.15, 662?673 (1978) · Zbl 0393.65014
[9]	Gilbert, J.R., Tarjan, R.E.: The analysis of a nested dissection algorithm. Numer. Math.50, 377?404 (1987) · Zbl 0645.65012
[10]	Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Appl. Math.36, 177?189 (1979) · Zbl 0432.05022
[11]	Liu, J.W.H.: The role of elimination trees in sparse factorization. Computer science report CS-87-12, York University, North York, Ontario 1987
[12]	Parter, S.: The use of linear graphs in Gauss elimination. SIAM Rev.3, 119?130 (1961) · Zbl 0102.11302
[13]	Pissanetzky, S.: Sparse matrix technology, Ed. Academic Press, London 1984 · Zbl 0536.65019
[14]	Roman, J.: Sur la renumérotation des n?uds 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, Université de Bordeaux I 1980
[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]	Roman, J.: Dissection emboîtée etn ?-théorème de séparation (1/2<?<1). Rapport interne Analyse appliquée et Informatique, Université de Bordeaux I (1984)
[17]	Roman, J.: Calculs de complexité relatifs à une méthode de dissection emboîtée. Numer. Math.47, 175?190 (1985) · Zbl 0537.65025
[18]	Roman, J.: Complexité d’algorithmes de séparation de graphes pour des implémentations séquentielles et réparties de l’élimination de Gauss. Thèse d’Etat, Université de Bordeaux I 1987
[19]	Roman, J., Durandeau, H.: Quelques modules de traitement des structures de données NDST et B. Résolution par méthode directe de systèmes linéaires de matrice symétrique définie positive de type dissections emboîtées. Rapport interne Analyse appliquée et Informatique, Université de Bordeaux I 1986
[20]	Rose, D.J.: A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations. In: Read, R.C. (ed.) Graph Theory Comput. pp. 183?217. New York: Academic Press 1973
[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
[22]	Schreiber, R.: A new implementation of sparse Gaussian elimination, ACM Trans. Math. Software8, 256?276 (1982) · Zbl 0491.65013
[23]	Vauquelin, B., Rubi, F., Roman, J., Lepine, J.M., Counilh M.C.: Description du calculateur CHEOPS. Rapport interne Informatique, Université de Bordeaux I (1986)
[24]	Présentation du Club MODULEF, Version 88, Brochure INRIA-MODULEF no 85 (Mai 1988)