The analysis of a nested dissection algorithm
DOI10.1007/BF01396660zbMATH Open0645.65012OpenAlexW2090129250MaRDI QIDQ1103322FDOQ1103322
Authors: J. R. Gilbert, Robert E. Tarjan 
Publication date: 1987
Published in: Numerische Mathematik (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/133161
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)
- Calculs de complexité relatifs à une méthode de dissection emboîtée
- Fast Nested Dissection for Finite Element Meshes
- scientific article; zbMATH DE number 4074330
- scientific article; zbMATH DE number 554763
topological graph theoryGauss eliminationsymmetric positive definite matricesfinite element graphsGeorge-Liu algorithmnested dissection algorithmseparators in planar graphssparse-contractible graphsparsity preservation
Direct numerical methods for linear systems and matrix inversion (65F05) Computational methods for sparse matrices (65F50) Planar graphs; geometric and topological aspects of graph theory (05C10)
Cites Work
- Title not available (Why is that?)
- Generalized Nested Dissection
- Nested Dissection of a Regular Finite Element Mesh
- Title not available (Why is that?)
- Decomposition of Finite Graphs Into Forests
- A Separator Theorem for Planar Graphs
- Algorithmic Aspects of Vertex Elimination on Graphs
- On the Problem of Partitioning Planar Graphs
- Computing the Minimum Fill-In is NP-Complete
- Title not available (Why is that?)
- The Use of Linear Graphs in Gauss Elimination
- A Separator Theorem for Chordal Graphs
- A separator theorem for graphs of bounded genus
- An Automatic Nested Dissection Algorithm for Irregular Finite Element Problems
Cited In (28)
- A Comparative Study of Linear and Semidefinite Branch-and-Cut Methods for Solving the Minimum Graph Bisection Problem
- A survey of direct methods for sparse linear systems
- Title not available (Why is that?)
- Customizable contraction hierarchies
- Analysis of Dehn's algorithm by critical pairs
- Compression, inversion, and approximate PCA of dense kernel matrices at near-linear computational complexity
- É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
- 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)
- Title not available (Why is that?)
- Efficient approximate solution of sparse linear systems
- On the stabbing number of a random Delaunay triangulation
- Search-space size in contraction hierarchies
- LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison
- Fast separator decomposition for finite element meshes
- Almost exact matchings
- Analysis of Knoop indentation
- Parallel computation of a Krylov matrix for a sparse and structured input
- Minimum fill-in: inapproximability and almost tight lower bounds
- Building graph separators with the recursive rotation algorithm for the nested dissection method
- Maximum matchings in geometric intersection graphs
- Communication lower bounds and optimal algorithms for numerical linear algebra
- Matrix sparsification and nested dissection over arbitrary fields
- Solution of sparse positive definite systems on a hypercube
- Tree decompositions and social graphs
- Graph bisection with Pareto optimization
- Calculs de complexité relatifs à une méthode de dissection emboîtée
- A parallel sparse direct solver via hierarchical DAG scheduling
Uses Software
This page was built for publication: The analysis of a nested dissection algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1103322)
