The analysis of a nested dissection algorithm

DOI10.1007/BF01396660zbMath0645.65012OpenAlexW2090129250MaRDI QIDQ1103322

John R. Gilbert, Robert Endre Tarjan

Publication date: 1987

Published in: Numerische Mathematik (Search for Journal in Brave)

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

zbMATH Keywords

Gauss eliminationsymmetric positive definite matricestopological graph theoryfinite element graphsGeorge-Liu algorithmnested dissection algorithmseparators in planar graphssparse-contractible graphsparsity preservation

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Planar graphs; geometric and topological aspects of graph theory (05C10) Direct numerical methods for linear systems and matrix inversion (65F05)

Related Items

Search-space size in contraction hierarchies, Parallel computation of a Krylov matrix for a sparse and structured input, On the stabbing number of a random Delaunay triangulation, LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison, A parallel graph partitioning algorithm for a message-passing multiprocessor, Algorithmique et calculs de complexité pour un solveur de type dissections emboîtées. (Algorithmic study and complexity bounds for a nested dissection solver), Solution of sparse positive definite systems on a hypercube, Efficient approximate solution of sparse linear systems, Graph Bisection with Pareto Optimization, Maximum matchings in geometric intersection graphs, A Comparative Study of Linear and Semidefinite Branch-and-Cut Methods for Solving the Minimum Graph Bisection Problem, Almost exact matchings, Fast separator decomposition for finite element meshes, É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, Compression, inversion, and approximate PCA of dense kernel matrices at near-linear computational complexity, A survey of direct methods for sparse linear systems, Communication lower bounds and optimal algorithms for numerical linear algebra, Minimum fill-in: inapproximability and almost tight lower bounds, Tree decompositions and social graphs, Customizable Contraction Hierarchies, A Parallel Sparse Direct Solver via Hierarchical DAG Scheduling

Uses Software

• symrcm

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A separator theorem for graphs of bounded genus
• The Use of Linear Graphs in Gauss Elimination
• A Separator Theorem for Chordal Graphs
• A Separator Theorem for Planar Graphs
• Generalized Nested Dissection
• Computing the Minimum Fill-In is NP-Complete
• On the Problem of Partitioning Planar Graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• An Automatic Nested Dissection Algorithm for Irregular Finite Element Problems
• Nested Dissection of a Regular Finite Element Mesh
• Decomposition of Finite Graphs Into Forests