Generalized Nested Dissection

DOI10.1137/0716027zbMath0435.65021OpenAlexW2113679823MaRDI QIDQ3875202

Richard J. Lipton, Robert Endre Tarjan, Donald J. Rose

Publication date: 1979

Published in: SIAM Journal on Numerical Analysis (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0716027

zbMATH Keywords

planar graphs sparse Gaussian elimination nested dissection sparse graphs separators symmetric positive definite matrix finite element problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Factorization of matrices (15A23) Graph theory (including graph drawing) in computer science (68R10) Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs (65N30) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Direct numerical methods for linear systems and matrix inversion (65F05)

Related Items

An Incomplete Cholesky Preconditioner Based on Orthogonal Approximations, Facial reduction for symmetry reduced semidefinite and doubly nonnegative programs, Maximum matchings in geometric intersection graphs, How to draw a planar clustered graph, A note on the SDP relaxation of the minimum cut problem, Quasiplanar graphs, string graphs, and the Erdős-Gallai problem, Hardness of graph-structured algebraic and symbolic problems, Fast separator decomposition for finite element meshes, Fast maximum likelihood estimation of very large spatial autoregressive models: a characteristic polynomial approach., Recursive conditioning, Min-max-boundary domain decomposition, A linear-time algorithm for symmetric convex drawings of internally triconnected plane graphs, A multilevel approach for trace system in HDG discretizations, Provably good mesh generation, Minimum Cuts in Surface Graphs, Planar and Toroidal Morphs Made Easier, A fast direct solver for nonlocal operators in wavelet coordinates, Finding small simple cycle separators for 2-connected planar graphs, Vecchia-Laplace approximations of generalized Gaussian processes for big non-Gaussian spatial data, Maximum matchings in planar graphs via Gaussian elimination, Supersonic viscous perfect gas flow past a circular cylinder, Efficient solutions of hierarchical systems of linear equations, Search-space size in contraction hierarchies, Parallel nested dissection for path algebra computations, A new approach to solving three combinatorial enumeration problems on planar graphs, Fast dynamic transitive closure with lookahead, Resolving Loads with Positive Interior Stresses, Parallel computation of a Krylov matrix for a sparse and structured input, Underestimated cost of targeted attacks on complex networks, Planar and toroidal morphs made easier, The analysis of a nested dissection algorithm, Separators and structure prediction in sparse orthogonal factorization, Domain decomposition based ${\mathcal H}$-LU preconditioning, A parallel graph partitioning algorithm for a message-passing multiprocessor, Treewidth for graphs with small chordality, Algorithms for multicommodity flows in planar graphs, A Fourier-accelerated volume integral method for elastoplastic contact, Local optimization on graphs, Solution of sparse positive definite systems on a hypercube, Efficient approximate solution of sparse linear systems, Graph Bisection with Pareto Optimization, Efficient algorithms for solving systems of linear equations and path problems, Fast shortest-paths algorithms in the presence of few destinations of negative-weight arcs, Solving Graph Laplacian Systems Through Recursive Partitioning and Two-Grid Preconditioning, On the negative cost girth problem in planar networks, Automating algorithm selection: checking for matrix properties that can simplify computations, Additive preconditioning and aggregation in matrix computations, Small grid embeddings of 3-polytopes, An Algebraic Sparsified Nested Dissection Algorithm Using Low-Rank Approximations, Almost exact matchings, Unnamed Item, Counting spanning trees using modular decomposition, Preconditioning for sparse linear systems at the dawn of the 21st century: history, current developments, and future perspectives, É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, Solving a Bernoulli type free boundary problem with random diffusion, Sparse direct factorizations through unassembled hyper-matrices, Counting and sampling minimum cuts in genus $g$ graphs, Transformations of matrix structures work again, Sparse shape functions for tetrahedral $p$-FEM using integrated Jacobi polynomials, A hysteretic multiscale formulation for nonlinear dynamic analysis of composite materials, Sparse Hierarchical Preconditioners Using Piecewise Smooth Approximations of Eigenvectors, Convex drawings of graphs with non-convex boundary constraints, Separator theorems and Turán-type results for planar intersection graphs, The MIN-cut and vertex separator problem, Not all planar digraphs have small cycle separators, Fast and efficient linear programming and linear least-squares computations, Eigenvector-Based Centrality Measures for Temporal Networks, Compression, inversion, and approximate PCA of dense kernel matrices at near-linear computational complexity, Fast Hierarchical Solvers For Sparse Matrices Using Extended Sparsification and Low-Rank Approximation, An algebraic multifrontal preconditioner that exploits the low‐rank property, Randomized preprocessing of homogeneous linear systems of equations, Edge separators for graphs of bounded genus with applications, A survey of direct methods for sparse linear systems, Efficient parallel factorization and solution of structured and unstructured linear systems, Shortest-path queries in static networks, On the ordering of sparse linear systems, Faster shortest-path algorithms for planar graphs, On factored discretizations of the Laplacian for the fast solution of Poisson's equation on general regions, New shape functions for triangular $p$-FEM using integrated Jacobi polynomials, A Separator Theorem for Chordal Graphs, Valid inequalities and lifting procedures for the shortest path problem in digraphs with negative cycles, Planar graphs, negative weight edges, shortest paths, and near linear time, Planar minimally rigid graphs and pseudo-triangulations, Single source shortest paths in $H$-minor free graphs, Unnamed Item, A Separator Theorem for String Graphs and its Applications, A Separator Theorem for String Graphs and Its Applications, Convexity-increasing morphs of planar graphs, Sparse semidefinite programs with guaranteed near-linear time complexity via dualized clique tree conversion, Dividing and conquering the square, Unnamed Item, Counting Spanning Trees in Graphs Using Modular Decomposition, Testing the necklace condition for shortest tours and optimal factors in the plane, Minimum fill-in: inapproximability and almost tight lower bounds, Many distances in planar graphs, Estimating the extremal eigenvalues of a symmetric matrix, Steady flow with separation past a thin airfoil at high Reynolds numbers, Efficient parallel linear programming, Fast and efficient solution of path algebra problems, Samplets: construction and scattered data compression, Calculs de complexité relatifs à une méthode de dissection emboîtée, Tractable minor-free generalization of planar zero-field Ising models, Refining an approximate inverse, Numerical linear algebra algorithms and software, Drawing plane graphs nicely, Unnamed Item, Symbolic and numeric methods for exploiting structure in constructing resultant matrices, Customizable Contraction Hierarchies, Flow in planar graphs with vertex capacities, PMORSy: parallel sparse matrix ordering software for fill-in minimization, Preconditioning techniques for large linear systems: A survey, $\mathcal{H}$-Matrix Based Second Moment Analysis for Rough Random Fields and Finite Element Discretizations