{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:25:15Z","timestamp":1787333115752,"version":"build-2736575974"},"reference-count":26,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>Parallel simulations at extreme scale require that the mesh is distributed across a large number of processors with equal work load and minimum interpart communications. A number of algorithms have been developed to meet these goals, e.g., graph\/hypergraph and coordinate-based methods. However, the global implementation of current approaches can fail on very large core counts, which is resolved by combining global and local partitioning using multiple parts per processor. The other limitation of graph\/hypergraph-based partitioning is that it uses one type of mesh entity as graph nodes; thus, the balance of other mesh entities may not be optimal. In the case of three-dimensional (3-D) linear finite element analysis, it is common to select mesh regions (elements) as partition objects. In current examples, the regions are well balanced up to 163,840 parts for a 1.07 billion element mesh, while the vertices have an imbalance which is as high as 19.52%. Two methods are developed that work in conjunction with graph\/hypergraph-based procedures to provide improved partitions. Example computations executed on an IBM Blue Gene\/P system using up to 163,840 cores demonstrate the usefulness of the procedures, particularly for time-critical calculations where individual cores may be lightly loaded in terms of the number of mesh entities per core. The algorithms presented in this paper reduced the vertex imbalance from 17.8% to 4.97% for a partition with 131,072 parts and accelerated the equation solution phase of the finite element analysis by 10.4%.<\/jats:p>","DOI":"10.1137\/090777323","type":"journal-article","created":{"date-parts":[[2010,11,9]],"date-time":"2010-11-09T18:51:20Z","timestamp":1289328680000},"page":"3201-3227","source":"Crossref","is-referenced-by-count":24,"title":["Controlling Unstructured Mesh Partitions for Massively Parallel Simulations"],"prefix":"10.1137","volume":"32","author":[{"given":"Min","family":"Zhou","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Onkar","family":"Sahni","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Karen D.","family":"Devine","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mark S.","family":"Shephard","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kenneth E.","family":"Jansen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2010,11,9]]},"reference":[{"key":"R1","unstructured":"E. Boman, K. Devine, L.A. Fisk, R. Heaphy, B. Hendrickson, V. Leung, C. Vaughan, U. Catalyurek, D. Bozdag, and W. Mitchell,\n                      Zoltan home page\n                      , available online at http:\/\/www.cs.sandia.gov\/Zoltan, 1999."},{"key":"R2","unstructured":"T. Bui and C. Jones,\n                      A heuristic for reducing fill in sparse matrix factorization\n                      , in Proceedings of the 6th SIAM Conference on Parallel Processing for Scientific Computing, SIAM, Philadelphia, 1993, pp. 445\u2013452."},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1109\/71.780863"},{"key":"R4","unstructured":"\u00dc.V. \u00c7ataly\u00fcrek and C. Aykanat,\n                      PaToH: A Multilevel Hypergraph Partitioning Tool, Version\n                      3.0, Department of Computer Engineering, Bilkent University, Ankara, 06533 Turkey. PaToH is available at http:\/\/bmi.osu.edu\/ umit\/software.htm, 1999."},{"key":"R5","doi-asserted-by":"crossref","unstructured":"K.D. Devine, E.G. Boman, R.T. Heaphy, R.H. Bisseling, and U.V. Catalyurek,\n                      Parallel hypergraph partitioning for scientific computing\n                      , in Proceedings of the 20th International Parallel and Distributed Processing Symposium (IPDPS'06), IEEE, Washington, DC, 2006, pp. 1\u201310.","DOI":"10.1109\/IPDPS.2006.1639359"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1109\/5992.988653"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"B. Hendrickson and R. Leland,\n                      A multilevel algorithm for partitioning graphs\n                      , in Proceedings of Supercomputing '95, ACM, New York, 1995, pp. 1\u201314.","DOI":"10.1145\/224170.224228"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/S0045-7825(00)00203-6"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"G. Karypis and V. Kumar,\n                      A parallel algorithm for multilevel graph partitioning and sparse matrix ordering\n                      , in Proceedings of the 10th International Parallel Processing Symposium, 1996, pp. 314\u2013319.","DOI":"10.1109\/IPPS.1996.508075"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"G. Karypis and V. Kumar,\n                      Multilevel algorithms for multi-constraint graph partitioning\n                      , in Proceedings of the 1998 ACM\/IEEE Conference on Supercomputing, ACM, New York, IEEE, Washington, DC, 1998, pp. 1\u201313.","DOI":"10.1109\/SC.1998.10018"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(00)00049-1"},{"key":"R13","unstructured":"F. Pellegrini,\n                      Scotch $5.0$ User's Guide\n                      , Technical report, LaBRI, Talence, France, 2007."},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1137\/0611030"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1007\/s003660200024"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1016\/j.cma.2005.10.018"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"O. Sahni, M. Zhou, M.S. Shephard, and K.E. Jansen,\n                      Scalable implicit finite element solver for massively parallel processing with demonstration to $160$k cores\n                      , in Proceedings of the IEEE\/ACM SC '09, IEEE, Washington, DC, ACM, New York, 2009, pp. 1\u201312. Finalist paper for the 2009 ACM Gordon Bell prize.","DOI":"10.1145\/1654059.1654129"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.605"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1007\/s00366-006-0048-4"},{"key":"R20","unstructured":"M.S. Shephard and E.S. Seol,\n                      Flexible distributed mesh data structure for parallel adaptive analysis\n                      , in Advanced Computational Infrastructures for Parallel and Distributed Adaptive Applications, John Wiley and Sons, New York, 2007, pp. 1\u201338."},{"key":"R21","doi-asserted-by":"crossref","unstructured":"H.D. Simon,\n                      Partitioning of unstructured problems for parallel processing\n                      , in Proceedings of the Conference on Parallel Methods on Large Scale Structural Analysis and Physics Applications, Pergammon Press, New York, 1991, pp. 135\u2013148.","DOI":"10.1016\/0956-0521(91)90014-V"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"J.D. Teresco, K.D. Devine, and J.E. Flaherty,\n                      Partitioning and dynamic load balancing for the numerical solution of partial differential equations\n                      , in Numerical Solution of Partial Differential Equations on Parallel Computers, Springer-Verlag, New York, 2005, pp. 55\u201381.","DOI":"10.1007\/3-540-31619-1_2"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"A. Trifunovic and W. J. Knottenbelt,\n                      Parkway\n                      2.0:\n                      A parallel multilevel hypergraph partitioning tool\n                      , in Proceedings of the 19th International Symposium on Computer and Information Sciences (ISCIS 2004), Lecture Notes in Comput. Sci. 3280, Springer, New York, 2004, pp. 789\u2013800.","DOI":"10.1007\/978-3-540-30182-0_79"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1016\/j.cma.2005.04.014"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1113\/jphysiol.1955.sp005276"},{"key":"R26","unstructured":"M. Zhou,\n                      Petascale Adaptive Computational Fluid Dynamics\n                      , Ph.D. thesis, Rensselaer Polytechnic Institute, Troy, NY, 2009."}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/090777323","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:33:37Z","timestamp":1787330017000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/090777323"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":26,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/090777323"],"URL":"https:\/\/doi.org\/10.1137\/090777323","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]}}}