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

DOI10.1007/BF01396049MaRDI QIDQ1114300zbMATH OpenOpenAlexFDO

Authors S. H. Smith

Publication date 1989

Published in Numerische Mathematik (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/133364

zbMATH Keywords

block storage schemecomplexityGauss eliminationlarge sparse systemsnested dissection methodNumerical experimentsseparator theorem

Mathematics Subject Classification ID

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

Review text

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.

Recommendations

• scientific article; zbMATH DE number 4074330
• Calculs de complexité relatifs à une méthode de dissection emboîtée
• The analysis of a nested dissection algorithm
• Étude de la séparation et de l'élimination sur une famille de graphes quotients déduite d'une méthode de dissections emboîtées
• Parallel nested dissection

Cites work

• A New Implementation of Sparse Gaussian Elimination
• A Separator Theorem for Planar Graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Algorithms for Matrix Partitioning and the Numerical Solution of Finite Element Systems
• An Automatic Nested Dissection Algorithm for Irregular Finite Element Problems
• An Optimal Agorithm for Symbolic Factorization of Symmetric Matrices
• Calculs de complexité relatifs à une méthode de dissection emboîtée
• scientific article; zbMATH DE number 3852305 (Why is no real title available?)
• scientific article; zbMATH DE number 3816913 (Why is no real title available?)
• Incomplete Nested Dissection for Solving n by n Grid Problems
• Nested Dissection of a Regular Finite Element Mesh
• Numerical Experiments Using Dissection Methods to Solve n by n Grid Problems
• The analysis of a nested dissection algorithm
• The Use of Linear Graphs in Gauss Elimination

Cited in

(8)

• The analysis of a nested dissection algorithm
• Étude de la séparation et de l'élimination sur une famille de graphes quotients déduite d'une méthode de dissections emboîtées
• scientific article; zbMATH DE number 4074330 (Why is no real title available?)
• Fast Nested Dissection for Finite Element Meshes
• scientific article; zbMATH DE number 878685 (Why is no real title available?)
• Reordering strategy for blocking optimization in sparse linear solvers
• Matrix sparsification and nested dissection over arbitrary fields
• Calculs de complexité relatifs à une méthode de dissection emboîtée

Describes a project that uses

Uses Software

• symrcm

This page was built for publication: Algorithmique et calculs de complexité pour un solveur de type dissections emboîtées. (Algorithmic study and complexity bounds for a nested dissection solver)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1114300)