An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations

DOI10.1137/0916028zbMATH Open0816.68093OpenAlexW1966461475MaRDI QIDQ4763752FDOQ4763752

Authors: Robert P. 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/

Recommendations

• An improved spectral bisection algorithm and its application to dynamic load balancing
• scientific article; zbMATH DE number 991436
• Min-max-boundary domain decomposition
• Partitioning graphs on message-passing machines by pairwise mincut
• A parallel graph partitioning algorithm for a message-passing multiprocessor

zbMATH Keywords

load balancingdistributed memory parallel computer

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Parallel numerical computation (65Y05) Graph theory (including graph drawing) in computer science (68R10)

Cited In (only showing first 100 items - show all)

• Evaluation of a Flow-Based Hypergraph Bipartitioning Algorithm
• Exploiting multiple levels of parallelism in sparse matrix-matrix multiplication
• Title not available (Why is that?)
• Title not available (Why is that?)
• Efficient algorithm for optimizing spectral partitions
• A numerical investigation of Schwarz domain decomposition techniques for elliptic problems on unstructured grids
• Relaxation-based coarsening for multilevel hypergraph partitioning
• Analysis of a Helmholtz preconditioning problem motivated by uncertainty quantification
• Eigenanalysis-based task mapping on parallel computers with cellular networks
• Graph reduction with spectral and cut guarantees
• The Effect of Various Sparsity Structures on Parallelism and Algorithms to Reveal Those Structures
• Approximating spectral clustering via sampling: a review
• Multiway \(p\)-spectral graph cuts on Grassmann manifolds
• Spectral clustering with physical intuition on spring-mass dynamics
• Tree-based coarsening and partitioning of complex networks
• Optimized quantum circuit partitioning
• Recursive spectral algorithms for automatic domain partitioning in parallel finite element analysis
• The effect of graph partitioning techniques on parallel block FSAI preconditioning: a computational study
• Title not available (Why is that?)
• Disentangling group and link persistence in dynamic stochastic block models
• A graph based Davidson algorithm for the graph partitioning problem
• Homogeneous grouping of non-prime steel products for online auctions: a case study
• Robust Multigrid Techniques for Augmented Lagrangian Preconditioning of Incompressible Stokes Equations with Extreme Viscosity Variations
• Sequential composition of linear systems' clans
• Optimality of spectral clustering in the Gaussian mixture model
• Title not available (Why is that?)
• How to divide a catchment to conquer its parallel processing. An efficient algorithm for the partitioning of water catchments
• Cavity flow characteristics and applications to kidney stone removal
• A framework for solving sequence problem of multiple input streams
• Improvements on spectral bisection
• COMBINING HELPFUL SETS AND PARALLEL SIMULATED ANNEALING FOR THE GRAPH-PARTITIONING PROBLEM∗
• Title not available (Why is that?)
• Effect of the storage format of sparse linear systems on parallel CFD computations
• Higher-order compatible finite element schemes for the nonlinear rotating shallow water equations on the sphere
• Network bipartitioning in the anti-communicability Euclidean space
• An efficient approach for large scale graph partitioning
• Parallel adaptive subspace correction schemes with applications to elasticity
• Parallel adaptation of general three-dimensional hybrid meshes
• A hybrid meta-heuristic for multi-objective optimization: MOSATS
• A unified framework of multi-objective cost functions for partitioning unstructured finite element meshes
• An efficient memetic algorithm for the graph partitioning problem
• Large-scale stabilized FE computational analysis of nonlinear steady-state transport/reaction systems
• A direct approach to conformational dynamics based on hybrid Monte Carlo
• Two improved algorithms for envelope and wavefront reduction
• An exact combinatorial algorithm for minimum graph bisection
• Parallel load balancing for dynamic execution environments
• A deterministic annealing algorithm for approximating a solution of the min-bisection problem
• Spectral partitioning with multiple eigenvectors
• Local expansion concepts for detecting transport barriers in dynamical systems
• Using domain decomposition to find graph bisectors
• Global optimization of nonconvex problems with multilinear intermediates
• Consistency of spectral clustering
• Parallel multilevel algorithms for hypergraph partitioning
• Direct graph \(k\)-partitioning with a Kernighan-Lin like heuristic
• The <scp>K‐partitioning</scp> problem: Formulations and <scp>branch‐and‐cut</scp>
• Lanczos-type variants of the COCR method for complex nonsymmetric linear systems
• Spectral bisection with two eigenvectors
• Speeding up a memetic algorithm for the max-bisection problem
• Latent semantic analysis and Fiedler retrieval
• State-defect constraint pairing graph coarsening method for Karush-Kuhn-Tucker matrices arising in orthogonal collocation methods for optimal control
• A new method, the fusion fission, for the relaxed \(k\)-way graph partitioning problem, and comparisons with some multilevel algorithms
• Multiphase mesh partitioning
• Bisection for parallel computing using Ritz and Fiedler vectors
• Geometric Separators for Finite-Element Meshes
• On the validity of a front-oriented approach to partitioning large sparse graphs with a connectivity constraint
• Higher-order moving mesh methods for PDE-constrained shape optimization
• Continuous quadratic programming formulations of optimization problems on graphs
• Isoperimetric Partitioning: A New Algorithm for Graph Partitioning
• Path optimization for graph partitioning problems
• A bounded-error quantum polynomial-time algorithm for two graph bisection problems
• Flow-Based Algorithms for Improving Clusters: A Unifying Framework, Software, and Performance
• Inexact overlapped block Broyden methods for solving nonlinear equations
• Dynamic load balancing in computational mechanics
• Load balancing for the parallel adaptive solution of partial differential equations
• Spectral partitioning works: planar graphs and finite element meshes
• Parallel dynamic load balancing strategies for adaptive irregular applications
• QMC Sampling from Empirical Datasets
• Iterative denoising
• The robust binomial approach to chance-constrained optimization problems with application to stochastic partitioning of large process networks
• A multilevel bilinear programming algorithm for the vertex separator problem
• On spectral bounds for the \(k\)-partitioning of graphs
• An experimental evaluation of local search heuristics for graph partitioning
• An exact approach for the multi-constraint graph partitioning problem
• Title not available (Why is that?)
• Dual multilevel optimization
• Min-max-boundary domain decomposition
• Combining clustered adaptive multistart and discrete dynamic convexized method for the max-cut problem
• High-quality surface remeshing using harmonic maps. II: Surfaces with high genus and of large aspect ratio
• Role of normalization in spectral clustering for stochastic blockmodels
• Spectral clustering and the high-dimensional stochastic blockmodel
• Spectral clustering and its use in bioinformatics
• Sparse direct factorizations through unassembled hyper-matrices
• Web document clustering using hyperlink structures
• Airspace sectorization with constraints
• Unstructured grid adaptation for multiscale finite volume method
• Co-clustering documents and words by minimizing the normalized cut objective function
• Parallel DNS algorithm on unstructured grids
• A first multilevel cooperative algorithm for capacitated multicommodity network design
• An efficient communications strategy for finite element methods on the Connection Machine CM-5 system
• Scalability of finite element applications on distributed-memory parallel computers

This page was built for publication: An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4763752)