An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations
From MaRDI portal
Publication:4763752
DOI10.1137/0916028zbMath0816.68093OpenAlexW1966461475MaRDI QIDQ4763752
Robert Patton Leland, Bruce A. Hendrickson
Publication date: 18 May 1995
Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)
Full work available at URL: https://digital.library.unt.edu/ark:/67531/metadc1186868/
Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Parallel numerical computation (65Y05)
Related Items (97)
Web document clustering using hyperlink structures ⋮ Flow-Based Algorithms for Improving Clusters: A Unifying Framework, Software, and Performance ⋮ A deterministic annealing algorithm for approximating a solution of the min-bisection problem ⋮ Multiway \(p\)-spectral graph cuts on Grassmann manifolds ⋮ Network bipartitioning in the anti-communicability Euclidean space ⋮ A unified framework of multi-objective cost functions for partitioning unstructured finite element meshes ⋮ Large-scale stabilized FE computational analysis of nonlinear steady-state transport/reaction systems ⋮ State-defect constraint pairing graph coarsening method for Karush-Kuhn-Tucker matrices arising in orthogonal collocation methods for optimal control ⋮ Continuous quadratic programming formulations of optimization problems on graphs ⋮ Load balancing for the parallel adaptive solution of partial differential equations ⋮ Unnamed Item ⋮ Lanczos-type variants of the COCR method for complex nonsymmetric linear systems ⋮ Unnamed Item ⋮ A hybrid meta-heuristic for multi-objective optimization: MOSATS ⋮ COMBINING HELPFUL SETS AND PARALLEL SIMULATED ANNEALING FOR THE GRAPH-PARTITIONING PROBLEM∗ ⋮ Homogeneous grouping of non-prime steel products for online auctions: a case study ⋮ Improvements on Spectral Bisection ⋮ BIFURCATION TRACKING ALGORITHMS AND SOFTWARE FOR LARGE SCALE APPLICATIONS ⋮ An efficient communications strategy for finite element methods on the Connection Machine CM-5 system ⋮ Direct graph \(k\)-partitioning with a Kernighan-Lin like heuristic ⋮ Scalability of finite element applications on distributed-memory parallel computers ⋮ Recursive spectral algorithms for automatic domain partitioning in parallel finite element analysis ⋮ Using domain decomposition to find graph bisectors ⋮ Two improved algorithms for envelope and wavefront reduction ⋮ Spectral partitioning works: planar graphs and finite element meshes ⋮ Latent semantic analysis and Fiedler retrieval ⋮ On the validity of a front-oriented approach to partitioning large sparse graphs with a connectivity constraint ⋮ Partitioning mathematical programs for parallel solution ⋮ Spectral clustering and its use in bioinformatics ⋮ An experimental evaluation of local search heuristics for graph partitioning ⋮ Higher-Order Moving Mesh Methods for PDE-Constrained Shape Optimization ⋮ Beyond good partition shapes: an analysis of diffusive graph partitioning ⋮ Spectral bisection with two eigenvectors ⋮ The <scp>K‐partitioning</scp> problem: Formulations and <scp>branch‐and‐cut</scp> ⋮ Robust Multigrid Techniques for Augmented Lagrangian Preconditioning of Incompressible Stokes Equations with Extreme Viscosity Variations ⋮ Iterative denoising ⋮ Consistency of spectral clustering ⋮ An exact algorithm for graph partitioning ⋮ A numerical investigation of Schwarz domain decomposition techniques for elliptic problems on unstructured grids ⋮ QMC Sampling from Empirical Datasets ⋮ Parallel multilevel algorithms for hypergraph partitioning ⋮ Sparse direct factorizations through unassembled hyper-matrices ⋮ Spectral clustering and the high-dimensional stochastic blockmodel ⋮ An exact approach for the multi-constraint graph partitioning problem ⋮ Co-clustering documents and words by minimizing the normalized cut objective function ⋮ Approximating Spectral Clustering via Sampling: A Review ⋮ Analysis of a Helmholtz preconditioning problem motivated by uncertainty quantification ⋮ The Effect of Various Sparsity Structures on Parallelism and Algorithms to Reveal Those Structures ⋮ Combining clustered adaptive multistart and discrete dynamic convexized method for the max-cut problem ⋮ Disentangling group and link persistence in dynamic stochastic block models ⋮ Dual multilevel optimization ⋮ A new method, the fusion fission, for the relaxed \(k\)-way graph partitioning problem, and comparisons with some multilevel algorithms ⋮ An efficient approach for large scale graph partitioning ⋮ A multilevel bilinear programming algorithm for the vertex separator problem ⋮ The robust binomial approach to chance-constrained optimization problems with application to stochastic partitioning of large process networks ⋮ Geometric Separators for Finite-Element Meshes ⋮ Parallel adaptation of general three-dimensional hybrid meshes ⋮ Higher-order compatible finite element schemes for the nonlinear rotating shallow water equations on the sphere ⋮ Unnamed Item ⋮ Unstructured grid adaptation for multiscale finite volume method ⋮ Quality meshing based on STL triangulations for biomedical simulations ⋮ A first multilevel cooperative algorithm for capacitated multicommodity network design ⋮ How to divide a catchment to conquer its parallel processing. An efficient algorithm for the partitioning of water catchments ⋮ An evaluation study of clustering algorithms in the scope of user communities assessment ⋮ Spectral clustering with physical intuition on spring-mass dynamics ⋮ Parallel dynamic load balancing strategies for adaptive irregular applications ⋮ Multiphase mesh partitioning ⋮ Local expansion concepts for detecting transport barriers in dynamical systems ⋮ Optimized quantum circuit partitioning ⋮ Sequential composition of linear systems' clans ⋮ Relaxation-Based Coarsening for Multilevel Hypergraph Partitioning ⋮ A FRAMEWORK FOR SOLVING SEQUENCE PROBLEM OF MULTIPLE INPUT STREAMS ⋮ Evaluation of a Flow-Based Hypergraph Bipartitioning Algorithm ⋮ An exact combinatorial algorithm for minimum graph bisection ⋮ A bounded-error quantum polynomial-time algorithm for two graph bisection problems ⋮ Cavity flow characteristics and applications to kidney stone removal ⋮ Optimality of spectral clustering in the Gaussian mixture model ⋮ Airspace sectorization with constraints ⋮ Spectral partitioning with multiple eigenvectors ⋮ Path optimization for graph partitioning problems ⋮ An efficient memetic algorithm for the graph partitioning problem ⋮ Unnamed Item ⋮ Exploiting Multiple Levels of Parallelism in Sparse Matrix-Matrix Multiplication ⋮ Parallel adaptive subspace correction schemes with applications to elasticity ⋮ Parallel DNS algorithm on unstructured grids ⋮ Dynamic load balancing in computational mechanics ⋮ Effect of the storage format of sparse linear systems on parallel CFD computations ⋮ A GRAPH BASED DAVIDSON ALGORITHM FOR THE GRAPH PARTITIONING PROBLEM ⋮ Parallel load balancing for dynamic execution environments ⋮ A direct approach to conformational dynamics based on hybrid Monte Carlo ⋮ The effect of graph partitioning techniques on parallel block FSAI preconditioning: a computational study ⋮ Inexact overlapped block Broyden methods for solving nonlinear equations ⋮ Tree-Based Coarsening and Partitioning of Complex Networks ⋮ Role of normalization in spectral clustering for stochastic blockmodels ⋮ Speeding up a memetic algorithm for the max-bisection problem ⋮ Global optimization of nonconvex problems with multilinear intermediates ⋮ High-quality surface remeshing using harmonic maps-Part II: Surfaces with high genus and of large aspect ratio
This page was built for publication: An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations
