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)

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.