{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,20]],"date-time":"2026-06-20T01:09:09Z","timestamp":1781917749889,"version":"3.54.5"},"reference-count":42,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2006,10,25]],"date-time":"2006-10-25T00:00:00Z","timestamp":1161734400000},"content-version":"vor","delay-in-days":4590,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Concurrency: Pract. Exper."],"published-print":{"date-parts":[[1994,4]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>If problems involving unstructured meshes are to be solved efficiently on distributed\u2010memory 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\u2010of\u2010magnitude improvement in run time on typical examples.<\/jats:p>","DOI":"10.1002\/cpe.4330060203","type":"journal-article","created":{"date-parts":[[2006,11,17]],"date-time":"2006-11-17T15:01:07Z","timestamp":1163775667000},"page":"101-117","source":"Crossref","is-referenced-by-count":276,"title":["Fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems"],"prefix":"10.1002","volume":"6","author":[{"given":"Stephen T.","family":"Barnard","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Horst D.","family":"Simon","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"311","published-online":{"date-parts":[[2006,10,25]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/0956-0521(91)90014-V"},{"key":"e_1_2_1_3_2","unstructured":"S.Hammond Mapping Unstructured Grid Computations to Massively Parallel Computers PhD thesis RPI June1992 RIACS Report 92.14."},{"key":"e_1_2_1_4_2","unstructured":"Z.Johan Data Parallel Finite Element Techniques for Large\u2010Scale Computational Fluid Dynamics PhD thesis Stanford University July1992."},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00129774"},{"key":"e_1_2_1_6_2","doi-asserted-by":"crossref","unstructured":"R.Das D. J.Mavriplis J.Saltz S.GuptaandR.Ponnusamy \u2018The design and implementation of parallel unstructured Euler solver using software primitives\u2019 in AIAA 30th Aerospace Sciences Meeting 1992 paper AIAA\u201092\u20100562.","DOI":"10.2514\/6.1992-562"},{"key":"e_1_2_1_7_2","doi-asserted-by":"crossref","unstructured":"R. D.Williams \u2018Performance of dynamic load balancing algorithms for unstructured mesh calculations\u2019 Technical Report C3P913 California Institute of Technology Pasadena California June1990.","DOI":"10.1002\/cpe.4330030502"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1002\/nme.1620360503"},{"key":"e_1_2_1_9_2","first-page":"871","volume-title":"The Laplacian Spectrum of Graphs","author":"Mohar B.","year":"1991"},{"key":"e_1_2_1_10_2","volume-title":"Eigenvalues in combinatorial optimization","author":"Mohar B.","year":"1992"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1137\/0611030"},{"key":"e_1_2_1_12_2","doi-asserted-by":"crossref","unstructured":"B.HendricksonandR.Leland \u2018An improved spectral graph partitioning algorithm for mapping parallel computations\u2019 Technical Report SAND92\u20101460 UC \u2010 405 Sandia Natl. Lab. Albuquerque NM September1992.","DOI":"10.2172\/6970738"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/0045-7949(88)90004-1"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/0045-7949(89)90046-1"},{"key":"e_1_2_1_15_2","unstructured":"Shang\u2010HuaTeng Points Spheres and Separators A Unified Geometric Approach to Graph Partitioning PhD thesis School of Computer Science Carnegie Mellon University Pittsburgh PA August1991."},{"key":"e_1_2_1_16_2","volume-title":"Automatic mesh partitioning","author":"Miller Gary L.","year":"1992"},{"key":"e_1_2_1_17_2","first-page":"209","volume-title":"Parallel Computations and their Impact on Mechanics, New York","author":"Nour\u2010Omid B.","year":"1986"},{"key":"e_1_2_1_18_2","unstructured":"NashatMansour Physical Optimization Algorithms for Mapping Data to Distributed\u2010Memory Multiprocessors.PhD thesis Department of Computer Science Syracuse University Syracuse NY August1992."},{"key":"e_1_2_1_19_2","first-page":"299","article-title":"Large step Markov chains for the traveling salesman problem","volume":"5","author":"Martin O.","year":"1991","journal-title":"Complex Systems"},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(92)90028-2"},{"key":"e_1_2_1_21_2","first-page":"113","volume-title":"Logic Synthesis and Silicon Compilation for VLSI","author":"Vincentelli A. Sangiovanni","year":"1987"},{"key":"e_1_2_1_22_2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-322-92106-2","volume-title":"Combinatorial Algorithms for Integrated Circuit Layout","author":"Lengauer T.","year":"1990"},{"key":"e_1_2_1_23_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.17.3.219"},{"key":"e_1_2_1_24_2","unstructured":"J.FrankleandR.Karp \u2018Circuit placements and cost bounds by eigenvector decomposition\u2019 in Proc. 1986 Conf. on CAD Santa Clara CA 1986 pp.414\u2013417."},{"issue":"9","key":"e_1_2_1_25_2","first-page":"1074","article-title":"New spectral methods for ratio cut partitioning and clustering","volume":"11","author":"Hagen Lars","year":"1992","journal-title":"IEEE Trans."},{"key":"e_1_2_1_26_2","doi-asserted-by":"crossref","unstructured":"P. K.Chan M.SchlagandJ.Zien \u2018Spectral k\u2010way ratio cut partitioning and clustering\u2019 inSymposium on Integrated Systems Seattle WA 1993(to be published).","DOI":"10.1145\/157485.165117"},{"issue":"127","key":"e_1_2_1_27_2","doi-asserted-by":"crossref","first-page":"679","DOI":"10.1090\/S0025-5718-1974-0405823-3","article-title":"The Rayleigh quotient iteration and some generalizations for nonnormal matrices","volume":"28","author":"Parlett B. N.","year":"1974","journal-title":"Math. Comp."},{"key":"e_1_2_1_28_2","volume-title":"The Symmetric Eigenvalue Problem","author":"Parlett B. N.","year":"1980"},{"key":"e_1_2_1_29_2","doi-asserted-by":"publisher","DOI":"10.1137\/0712047"},{"key":"e_1_2_1_30_2","doi-asserted-by":"publisher","DOI":"10.2307\/2007654"},{"key":"e_1_2_1_31_2","doi-asserted-by":"publisher","DOI":"10.1137\/0904019"},{"key":"e_1_2_1_32_2","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9991(89)90109-5"},{"key":"e_1_2_1_33_2","unstructured":"J. G.Lewis Algorithms for Sparse Matrix Eigenvalue Problems PhD thesis Stanford University Department of Computer Science 1977."},{"key":"e_1_2_1_34_2","doi-asserted-by":"publisher","DOI":"10.1137\/0725078"},{"key":"e_1_2_1_35_2","doi-asserted-by":"crossref","unstructured":"D.Eppstein Z.Galil G.ItalianoandA.Nissenzweig \u2018Sparsification\u2014a technique for speeding up dynamic graph algorithms\u2019 in Proceedings of FOCS '92 1992.","DOI":"10.1109\/SFCS.1992.267818"},{"key":"e_1_2_1_36_2","doi-asserted-by":"publisher","DOI":"10.21136\/CMJ.1973.101168"},{"key":"e_1_2_1_37_2","doi-asserted-by":"publisher","DOI":"10.21136\/CMJ.1975.101356"},{"issue":"100","key":"e_1_2_1_38_2","doi-asserted-by":"crossref","first-page":"619","DOI":"10.21136\/CMJ.1975.101357","article-title":"A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory","volume":"25","author":"Fiedler M.","year":"1975","journal-title":"Czechoslovak Math. J."},{"key":"e_1_2_1_39_2","doi-asserted-by":"crossref","unstructured":"R. B.Boppana \u2018Eigenvalues and graph bisection: an average case analysis\u2019 in 28th Annual Symp. Found. Comp. Sci 1987 pp.280\u2013285.","DOI":"10.1109\/SFCS.1987.22"},{"key":"e_1_2_1_40_2","doi-asserted-by":"publisher","DOI":"10.1137\/0609021"},{"key":"e_1_2_1_41_2","volume-title":"A projection technique for partitioning the nodes of a graph","author":"Rendl F.","year":"1990"},{"key":"e_1_2_1_42_2","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1970.tb01770.x"},{"key":"e_1_2_1_43_2","doi-asserted-by":"publisher","DOI":"10.2307\/2007471"}],"container-title":["Concurrency: Practice and Experience"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fcpe.4330060203","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/cpe.4330060203","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,25]],"date-time":"2023-10-25T08:29:07Z","timestamp":1698222547000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/cpe.4330060203"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,4]]},"references-count":42,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1994,4]]}},"alternative-id":["10.1002\/cpe.4330060203"],"URL":"https:\/\/doi.org\/10.1002\/cpe.4330060203","archive":["Portico"],"relation":{},"ISSN":["1040-3108","1096-9128"],"issn-type":[{"value":"1040-3108","type":"print"},{"value":"1096-9128","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,4]]}}}