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 (21)

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

This page was built for publication: The analysis of a nested dissection algorithm