Geometric Separators for Finite-Element Meshes

DOI10.1137/S1064827594262613zbMath0914.65123OpenAlexW1997631839MaRDI QIDQ4389247

William P. Thurston, Gary Lee Miller, Stephen A. Vavasis, Shang-Hua Teng

Publication date: 12 May 1998

Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)

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

zbMATH Keywords

algorithmcomputational complexityfinite elementsdomain decompositionmesh partitioning

Mathematics Subject Classification ID

Multigrid methods; domain decomposition for boundary value problems involving PDEs (65N55) Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs (65N30) Complexity and performance of numerical algorithms (65Y20)

Related Items (23)

Continuous quadratic programming formulations of optimization problems on graphs ⋮ Spectral partitioning works: planar graphs and finite element meshes ⋮ Facial reduction for symmetry reduced semidefinite and doubly nonnegative programs ⋮ A note on the SDP relaxation of the minimum cut problem ⋮ On weighted sublinear separators ⋮ Grad and classes with bounded expansion. II: Algorithmic aspects ⋮ Non-existence of annular separators in geometric graphs ⋮ Optimal cache-oblivious mesh layouts ⋮ Network Essence: PageRank Completion and Centrality-Conforming Markov Chains ⋮ Vulnerability of nearest neighbor graphs ⋮ Metric uniformization and spectral bounds for graphs ⋮ Efficient Mapping of High Order Basis Sets for Unbounded Domains ⋮ The MIN-cut and vertex separator problem ⋮ A multilevel bilinear programming algorithm for the vertex separator problem ⋮ Provably Good Partitioning and Load Balancing Algorithms for Parallel Adaptive N-Body Simulation ⋮ The vertex separator problem: a polyhedral investigation ⋮ Simple and optimal output-sensitive construction of contour trees using monotone paths ⋮ Min-max-boundary domain decomposition ⋮ UNSTRUCTURED MESH GENERATION: THEORY, PRACTICE, AND PERSPECTIVES ⋮ A Glimpse into Thurston’s Work ⋮ Edge integrity of nearest neighbor graphs and separator theorems ⋮ Sublinear Separators in Intersection Graphs of Convex Shapes ⋮ Upper eigenvalue bounds for the Kirchhoff Laplacian on embedded metric graphs

Cites Work

• Provably good mesh generation
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Coverings of Bipartite Graphs
• Automatic Domain Partitioning in Three Dimensions
• Partitioning Sparse Matrices with Eigenvectors of Graphs
• An Iterative Method for Elliptic Problems on Regions Partitioned into Substructures
• Separators for sphere-packings and nearest neighbor graphs
• An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations
• Stable Finite Elements for Problems with Wild Coefficients
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Geometric Separators for Finite-Element Meshes