Abstract
Efficient use of a distributed memory parallel computer requires that the computational load be balanced across processors in a way that minimizes interprocessor communication. A new domain mapping algorithm is presented that extends recent work in which ideas from spectral graph theory have been applied to this problem. The generalization of spectral graph bisection involves a novel use of multiple eigenvectors to allow for division of a computation into four or eight parts at each stage of a recursive decomposition. The resulting method is suitable for scientific computations like irregular finite elements or differences performed on hypercube or mesh architecture machines. Experimental results confirm that the new method provides better decompositions arrived at more economically and robustly than with previous spectral methods. This algorithm allows for arbitrary nonnegative weights on both vertices and edges to model inhomogeneous computation and communication. A new spectral lower bound for graph bisection is also presented.
Keywords
ComputationHypercubeAlgorithmGraph partitionSpectral graph theoryDomain decomposition methodsBisection methodGraphSpectral methodComputer scienceMathematicsEigenvalues and eigenvectorsGeneralizationHypercube graphParallel computingTheoretical computer scienceVoltage graphFinite element methodLine graph
Affiliated Institutions
Related Publications
Reentrant polygon clipping
A new family of clipping algorithms is described. These algorithms are able to clip polygons against irregular convex plane-faced volumes in three dimensions, removing the parts...
Partitioning Sparse Matrices with Eigenvectors of Graphs
The problem of computing a small vertex separator in a graph arises in the context of computing a good ordering for the parallel factorization of sparse, symmetric matrices. An ...
Expander codes
Using expander graphs, we construct a new family of asymptotically good, linear error-correcting codes. These codes have linear time sequential decoding algorithms and logarithm...
AMBERCUBE MD, parallelization of Amber's molecular dynamics module for distributed‐memory hypercube computers
Abstract A fully functional parallel version of the molecular dynamics (MD) module of AMBER3a has been implemented. Procedures parallelized include the calculation of the long‐r...
<i>Ab initio</i>effective potentials for use in molecular quantum mechanics
We have investigated the method of effective potentials for replacing the core electrons in molecular calculations. The effective potential has been formulated in a way which si...
Publication Info
- Year
- 1995
- Type
- article
- Volume
- 16
- Issue
- 2
- Pages
- 452-469
- Citations
- 481
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
481
OpenAlex
Cite This
Bruce Hendrickson,
Robert W. Leland
(1995).
An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations.
SIAM Journal on Scientific Computing
, 16
(2)
, 452-469.
https://doi.org/10.1137/0916028
Identifiers
- DOI
- 10.1137/0916028