Generalized Nested Dissection
From MaRDI portal
Publication:3875202
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
planar graphssparse Gaussian eliminationnested dissectionsparse graphsseparatorssymmetric positive definite matrixfinite element problems
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 (only showing first 100 items - show all)
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 ⋮ OBDDs of a monotone function and of its prime implicants ⋮ 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
This page was built for publication: Generalized Nested Dissection
