{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,5]],"date-time":"2025-03-05T05:33:25Z","timestamp":1741152805087,"version":"3.38.0"},"reference-count":29,"publisher":"SAGE Publications","issue":"4","license":[{"start":{"date-parts":[[1995,12,1]],"date-time":"1995-12-01T00:00:00Z","timestamp":817776000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["The International Journal of Supercomputer Applications and High Performance Computing"],"published-print":{"date-parts":[[1995,12]]},"abstract":"<jats:p> A new method is described for optimizing graph parti tions that arise in mapping unstructured mesh calcula tions to parallel computers. The method employs a combination of iterative techniques to evenly balance the workload and minimize the number and volume of interprocessor communications. When combined with a fast direct-partitioning technique (such as the Greedy algorithm) to give an initial partition, the resulting two- stage process proves itself to be a powerful and flexi ble solution to the static graph-partitioning problem. A clustering technique can also be employed to speed up the whole process. Experiments, on graphs with up to a million nodes, indicate that the resulting code is up to an order of magnitude faster than existing state- of-the-art techniques such as Multilevel Recursive Spectral Bisection, while providing partitions of equiv alent quality. <\/jats:p>","DOI":"10.1177\/109434209500900403","type":"journal-article","created":{"date-parts":[[2007,3,11]],"date-time":"2007-03-11T07:54:27Z","timestamp":1173599667000},"page":"280-295","source":"Crossref","is-referenced-by-count":41,"title":["A Localized Algorithm for Optimizing Unstructured Mesh Partitions"],"prefix":"10.1177","volume":"9","author":[{"given":"Chris H.","family":"Walshaw","sequence":"first","affiliation":[{"name":"SCHOOL OF COMPUTING AND MATHEMATICAL SCIENCES UNIVERSITY\rOF GREENWICH LONDON, SE18 6PF U.K."}]},{"given":"Mark","family":"Cross","sequence":"additional","affiliation":[{"name":"SCHOOL OF COMPUTING AND MATHEMATICAL SCIENCES UNIVERSITY\rOF GREENWICH LONDON, SE18 6PF U.K."}]},{"given":"Martin G.","family":"Everett","sequence":"additional","affiliation":[{"name":"SCHOOL OF COMPUTING AND MATHEMATICAL SCIENCES UNIVERSITY\rOF GREENWICH LONDON, SE18 6PF U.K."}]}],"member":"179","published-online":{"date-parts":[[1995,12,1]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.4330060203"},{"volume-title":"Parallel and distributed computation: Numerical methods","year":"1989","author":"Bertsekas, D.P.","key":"atypb2"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(89)90021-X"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/0045-7949(88)90004-1"},{"volume-title":"TOP\/DOMDEC-a software tool for mesh partitioning and parallel processing. Technical Report RNR-93-011","year":"1993","author":"Farhat, C.","key":"atypb5"},{"key":"atypb6","doi-asserted-by":"crossref","unstructured":"Fiduccia, C.M., and Mattheyses, R.M. 1982. A linear time heuristic for improving network partitions. In Proc. 19th IEEE Design Automatian Conference . Piscataway, NJ: IEEE , pp. 175-181.","DOI":"10.1145\/800263.809204"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1007\/BF01388998"},{"key":"atypb8","first-page":"93","author":"Hendrickson, B.","year":"1993","journal-title":"Technical Report SAND"},{"key":"atypb9","unstructured":"Albuquerque, NM: Sandia National Labs."},{"volume-title":"Scalability of finite element applications on distributed memory parallel computers. Technical Report TR-16-94","year":"1994","author":"Johan, Z.","key":"atypb10"},{"volume-title":"Mapping unstructured mesh codes onto local memory parallel architectures. Ph.D. thesis. University of Greenwich","year":"1994","author":"Jones, B.W.","key":"atypb11"},{"volume-title":"A fast and high quality multilevel scheme for partitioning irregular graphs. Technical Report TR95-035","year":"1995","author":"Karypis, G.","key":"atypb12"},{"volume-title":"Analysis of multilevel graph partitioning. Technical Report TR95-037","year":"1995","author":"Karypis, G.","key":"atypb13"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1970.tb01770.x"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1126\/science.220.4598.671"},{"volume-title":"A parallelizable load balancing algorithm. Technical Report AIAA-93-0061","year":"1993","author":"L\u00f6hner, R.","key":"atypb16"},{"volume-title":"Integrated flow and stress using an unstructured mesh on distributed memory parallel systems. In Parallel CFD'94","year":"1995","author":"McManus, K.","key":"atypb17"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"Savage, J., and Wloka, M. 1991. Parallelism in graph partitioning. J. Par. Dist. Comput. 13:257-272. Shivaratri, N. G.","DOI":"10.1016\/0743-7315(91)90074-J"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1109\/2.179115"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(94)90120-1"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1109\/31.1742"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1002\/nme.1620380306"},{"key":"atypb23","unstructured":"Vanderstraeten, D., Keunings, R., and Farhat, C. 1995a. Beyond conventional mesh partitioning algorithms and the minimum edge cut criterion: impact on realistic applications. In Parallel Processing for Scientific Computing , edited by D. Bailey et al. Philadelphia: SIAM, pp. 611-614."},{"key":"atypb24","doi-asserted-by":"crossref","unstructured":"Vanderstraeten, D., Keunings, R., and Farhat, C. 1995b. Optimization of mesh partitions and impact on parallel CFD. In Parallel computational fluid dynamics: New trends and advances, edited by A. Ecer, et al. Amsterdam: Elsevier, pp. 233-239.","DOI":"10.1016\/B978-044481999-4\/50154-7"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.4330070103"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-60321-2_10"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-6130-6_2"},{"volume-title":"JOSTLE: Partitioning of unstructured meshes for massively parallel machines. In Parallel CFD '94","year":"1995","author":"Walshaw, C.","key":"atypb28"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.4330030502"}],"container-title":["The International Journal of Supercomputer Applications and High Performance Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/109434209500900403","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/109434209500900403","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,4]],"date-time":"2025-03-04T10:42:40Z","timestamp":1741084960000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/109434209500900403"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,12]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1995,12]]}},"alternative-id":["10.1177\/109434209500900403"],"URL":"https:\/\/doi.org\/10.1177\/109434209500900403","relation":{},"ISSN":["1078-3482"],"issn-type":[{"type":"print","value":"1078-3482"}],"subject":[],"published":{"date-parts":[[1995,12]]}}}