The DOI matches its Crossref record; 10 of the 10 references it cites were found in a registry or an index.
An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
An Efficient Heuristic Procedure for Partitioning Graphs
Kernighan, B. W., & Lin, S. (1970) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1970.tb01770.x · Cited by 5,305
Algebraic connectivity of graphs
Fiedler, M. (1973) · Czechoslovak Mathematical Journal · doi:10.21136/cmj.1973.101168 · Cited by 3,977
Some simplified NP-complete graph problems
Garey, M. R., Johnson, D. S., & Stockmeyer, L. (1976) · Theoretical Computer Science · doi:10.1016/0304-3975(76)90059-1 · Cited by 2,059
Partitioning Sparse Matrices with Eigenvectors of Graphs
Pothen, A., Simon, H. D., & Liou, K.-P. (1990) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/0611030 · Cited by 1,684
The Symmetric Eigenvalue Problem.
Wilkinson, J. H., & Parlett, B. N. (1981) · Mathematics of Computation · doi:10.2307/2007453 · Cited by 1,186
A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory
Fiedler, M. (1975) · Czechoslovak Mathematical Journal · doi:10.21136/cmj.1975.101357 · Cited by 1,042
Lower Bounds for the Partitioning of Graphs
Donath, W. E., & Hoffman, A. J. (1973) · IBM Journal of Research and Development · doi:10.1147/rd.175.0420 · Cited by 660
Numerical Methods for Unconstrained Optimization and Nonlinear Equations.
Kass, R. E., Dennis, J. E., & Schnabel, R. B. (1985) · Journal of the American Statistical Association · doi:10.2307/2288097 · Cited by 602
An algorithm for quadrisection and its application to standard cell placement
Suaris, P., & Kedem, G. (1988) · IEEE Transactions on Circuits and Systems · doi:10.1109/31.1742 · Cited by 106
On the determination of χl,η+−0 AND η000 from bubble chamber measurements
Votruba, J. (1975) · Czechoslovak Journal of Physics · doi:10.1007/bf01591018 · Cited by 96
Cited by
Fast Parallel Algorithms for Short-Range Molecular Dynamics
Plimpton, S. (1995) · Journal of Computational Physics · doi:10.1006/jcph.1995.1039 · Cited by 44,721
Iterative Methods for Sparse Linear Systems
Saad, Y. (2003) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9780898718003 · Cited by 13,790
A tutorial on spectral clustering
von Luxburg, U. (2007) · Statistics and Computing · doi:10.1007/s11222-007-9033-z · Cited by 10,349
A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
Karypis, G., & Kumar, V. (1998) · SIAM Journal on Scientific Computing · doi:10.1137/s1064827595287997 · Cited by 5,762
Near linear time algorithm to detect community structures in large-scale networks
Raghavan, U. N., Albert, R., & Kumara, S. (2007) · Physical Review E · doi:10.1103/physreve.76.036106 · Cited by 3,502
Metadata
- Authors
- Hendrickson, B., & Leland, R.
- Venue
- SIAM Journal on Scientific Computing
- Published
- 1995-03
- Volume
- 16
- Issue
- 2
- Pages
- 452-469
- ISSN
- 1064-8275 (ISSN-L)
- 1095-7197
- OpenAlex
- W1966461475
- Cited by
- 480
- References
- 10
- FWCI
- 38.76
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.