Calculs de complexité relatifs à une méthode de dissection emboîtée

DOI10.1007/BF01389708MaRDI QIDQ792734zbMATH OpenOpenAlexFDO

Authors N. E. Zubov

Publication date 1985

Published in Numerische Mathematik (Search for Journal in Brave)

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

zbMATH Keywords

finite element methodGaussian eliminationnested dissectionnumerical resultsplanar graphseparatorsparse matrix

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

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.

Recommendations

• 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; zbMATH DE number 4074330
• The analysis of a nested dissection algorithm
• scientific article; zbMATH DE number 4030966
• scientific article; zbMATH DE number 741125

Cites work

• A Separator Theorem for Planar Graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• An Algorithm for Reducing the Bandwidth and Profile of a Sparse Matrix
• Generalized Nested Dissection
• scientific article; zbMATH DE number 3816913 (Why is no real title available?)
• scientific article; zbMATH DE number 3903903 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3518832 (Why is no real title available?)
• Nested Dissection of a Regular Finite Element Mesh
• The Use of Linear Graphs in Gauss Elimination

Cited in

(11)

• Efficient solutions of hierarchical systems of linear equations
• The analysis of a nested dissection algorithm
• 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; zbMATH DE number 3900092 (Why is no real title available?)
• scientific article; zbMATH DE number 4030966 (Why is no real title available?)
• É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?)
• A Note on Nested Dissection for Rectangular Grids
• Fast Nested Dissection for Finite Element Meshes
• scientific article; zbMATH DE number 1106568 (Why is no real title available?)
• scientific article; zbMATH DE number 878685 (Why is no real title available?)

Describes a project that uses

Uses Software

• symrcm

This page was built for publication: Calculs de complexité relatifs à une méthode de dissection emboîtée

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