The DOI matches its Crossref record; 23 of the 23 references it cites were found in a registry or an index.
Fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems
Abstract
If problems involving unstructured meshes are to be solved efficiently on distributed‐memory parallel computers, the meshes must be partitioned and distributed across processors in a way that balances the computational load and minimizes communication. The recursive spectral bisection method (RSB) has been shown to be very effective for such partitioning problems compared to alternative methods, but RSB in its simplest form is expensive. Here a multilevel version of RSB is introduced that attains about an order‐of‐magnitude improvement in run time on typical examples.
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
The Symmetric Eigenvalue Problem
Parlett, B. N. (1998) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611971163 · Cited by 3,192
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
Self-citationSolution of Sparse Indefinite Systems of Linear Equations
Paige, C. C., & Saunders, M. A. (1975) · SIAM Journal on Numerical Analysis · doi:10.1137/0712047 · Cited by 1,620
New spectral methods for ratio cut partitioning and clustering
Hagen, L., & Kahng, A. B. (1992) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/43.159993 · Cited by 1,288
The Symmetric Eigenvalue Problem.
Wilkinson, J. H., & Parlett, B. N. (1981) · Mathematics of Computation · doi:10.2307/2007453 · Cited by 1,186
THE LAPLACIAN SPECTRUM OF GRAPHS y
Mohar, B. (1991) · Cited by 1,090
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
The Laplacian spectrum of graphs
Newman, M. (2001) · Library and Archives Canada (Government of Canada) · Cited by 674
An r-Dimensional Quadratic Placement Algorithm
Hall, K. M. (1970) · Management Science · doi:10.1287/mnsc.17.3.219 · Cited by 522
An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations
Hendrickson, B., & Leland, R. (1995) · SIAM Journal on Scientific Computing · doi:10.1137/0916028 · Cited by 480
Spectral K-way ratio-cut partitioning and clustering
Chan, P. K., Schlag, M. D. F., & Zien, J. Y. (1994) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/43.310898 · Cited by 442
Performance of dynamic load balancing algorithms for unstructured mesh calculations
Williams, R. D. (1991) · Concurrency: Practice and Experience · doi:10.1002/cpe.4330030502 · Cited by 345
Large-step Markov chains for the Traveling Salesman Problem
Martin, O. (2018) · doi:10.6083/nk322d67m · Cited by 321
On Minimizing the Maximum Eigenvalue of a Symmetric Matrix
Overton, M. L. (1988) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/0609021 · Cited by 206
Large-step markov chains for the TSP incorporating local search heuristics
Martin, O., Otto, S. W., & Felten, E. W. (1992) · Operations Research Letters · doi:10.1016/0167-6377(92)90028-2 · Cited by 201
Farhat, C., & Lesoinne, M. (1993) · International Journal for Numerical Methods in Engineering · doi:10.1002/nme.1620360503 · Cited by 193
Eigenvalues in Combinatorial Optimization
Mohar, B., & Poljak, S. (1993) · The IMA volumes in mathematics and its applications · doi:10.1007/978-1-4613-8354-3_5 · Cited by 140
Miller, G. L., Teng, S., Thurston, W. P. H., & Vavasis, S. A. (1993) · The IMA volumes in mathematics and its applications · doi:10.1007/978-1-4613-8369-7_3 · Cited by 138
Spectral K -way ratio-cut partitioning and clustering
Chan, P. K., Schlag, M. D. F., & Zien, J. Y. (1993) · ACM/IEEE Design Automation Conference (DAC) · doi:10.1145/157485.165117 · Cited by 127
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
A mesh refinement method for 𝐴𝑥=𝜆𝐵𝑥
McCormick, S. F. (1981) · Mathematics of Computation · doi:10.1090/s0025-5718-1981-0606508-4 · Cited by 8
Cited by
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
Shuman, D. I., Narang, S. K., Frossard, P., Ortega, A., & Vandergheynst, P. (2013) · IEEE Signal Processing Magazine · doi:10.1109/msp.2012.2235192 · Cited by 4,421
Multilevelk-way Partitioning Scheme for Irregular Graphs
Karypis, G., & Kumar, V. (1998) · Journal of Parallel and Distributed Computing · doi:10.1006/jpdc.1997.1404 · Cited by 1,675
Direct Methods for Sparse Matrices
Duff, I. S., Erisman, A. M., & Reid, J. K. (2017) · doi:10.1093/acprof:oso/9780198508380.001.0001 · Cited by 1,604
A multilevel algorithm for partitioning graphs
Hendrickson, B., & Leland, R. (1995) · Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM) - Supercomputing '95 · doi:10.1145/224170.224228 · Cited by 1,069
Metadata
- Authors
- Barnard, S. T., & Simon, H. D.
- Venue
- Concurrency: Practice and Experience
- Publisher
- Wiley
- Published
- 1994-04
- Volume
- 6
- Issue
- 2
- Pages
- 101-117
- ISSN
- 1040-3108 (ISSN-L)
- 1096-9128
- OpenAlex
- W1981893977
- Cited by
- 488
- References
- 23
- FWCI
- 40.02
- 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.