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

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

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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