Algorithmique et calculs de complexité pour un solveur de type dissections emboîtées. (Algorithmic study and complexity bounds for a nested dissection solver) (Q1114300): Difference between revisions
From MaRDI portal
Latest revision as of 09:55, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Algorithmique et calculs de complexité pour un solveur de type dissections emboîtées. (Algorithmic study and complexity bounds for a nested dissection solver) |
scientific article |
Statements
Algorithmique et calculs de complexité pour un solveur de type dissections emboîtées. (Algorithmic study and complexity bounds for a nested dissection solver) (English)
0 references
1989
0 references
We consider the nested dissection method based on separator theorems introduced by \textit{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 \textit{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.
0 references
Gauss elimination
0 references
separator theorem
0 references
complexity
0 references
nested dissection method
0 references
large sparse systems
0 references
block storage scheme
0 references
Numerical experiments
0 references
0 references
0 references