{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,26]],"date-time":"2026-08-26T01:59:13Z","timestamp":1787709553765,"version":"build-2784847793"},"reference-count":52,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>We consider two-dimensional partitioning of general sparse matrices for parallel sparse matrix-vector multiply operation. We present three hypergraph-partitioning-based methods, each having unique advantages. The first one treats the nonzeros of the matrix individually and hence produces fine-grain partitions. The other two produce coarser partitions, where one of them imposes a limit on the number of messages sent and received by a single processor, and the other trades that limit for a lower communication volume. We also present a thorough experimental evaluation of the proposed two-dimensional partitioning methods together with the hypergraph-based one-dimensional partitioning methods, using an extensive set of public domain matrices. Furthermore, for the users of these partitioning methods, we present a partitioning recipe that chooses one of the partitioning methods according to some matrix characteristics.<\/jats:p>","DOI":"10.1137\/080737770","type":"journal-article","created":{"date-parts":[[2010,2,24]],"date-time":"2010-02-24T18:06:15Z","timestamp":1267034775000},"page":"656-683","source":"Crossref","is-referenced-by-count":87,"title":["On Two-Dimensional Sparse Matrix Partitioning: Models, Methods, and a Recipe"],"prefix":"10.1137","volume":"32","author":[{"given":"\u00dcmt V.","family":"\u00c7ataly\u00fcrek","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Cevdet","family":"Aykanat","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bora","family":"U\u00e7ar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2010,2,24]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2007.09.006"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(01)00099-0"},{"key":"R3","first-page":"47","volume":"21","author":"Bisseling R. H.","year":"2005","journal-title":"Electron. Trans. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/1097-4067","issn-type":"print"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(92)90013-D"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1145\/175276.175279"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"U. V. Catalyurek, E. G. Boman, K. D. Devine, D. Bozda\u011f, R. Heaphy, and L. A. Fisk,\n                      Hypergraph-based dynamic load balancing for adaptive scientific computations\n                      , in Proceedings of the 21st International Parallel and Distributed Processing Symposium (IPDPS), 2007, IEEE.","DOI":"10.1109\/IPDPS.2007.370258"},{"key":"R7","unstructured":"U. V. \u00c7ataly\u00fcrek,\n                      Hypergraph Models for Sparse Matrix Partitioning and Reordering\n                      , Ph.D. thesis, Bilkent University, Computer Engineering and Information Science, Ankara, Turkey, 1999, http:\/\/www.cs.bilkent.edu.tr\/tech-reports\/1999\/ABSTRACTS.1999.html."},{"key":"R8","doi-asserted-by":"crossref","unstructured":"U. V. \u00c7ataly\u00fcrek and C. Aykanat,\n                      Decomposing irregularly sparse matrices for parallel matrix-vector multiplications\n                      , in Proceedings of the 3rd International Symposium on Solving Irregularly Structured Problems in Parallel, Irregular'96, Lecture Notes in Comput. Sci. 1117, Springer-Verlag, New York, 1996, pp. 75\u201386.","DOI":"10.1007\/BFb0030098"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1109\/71.780863"},{"key":"R10","unstructured":"U. V. \u00c7ataly\u00fcrek and C. Aykanat,\n                      PaToH: A Multilevel Hypergraph Partitioning Tool, Version\n                      3.0, Bilkent University, Department of Computer Engineering, Ankara, Turkey, 1999. PaToH is available at http:\/\/bmi.osu.edu\/~umit\/software.htm."},{"key":"R11","unstructured":"U. V. \u00c7ataly\u00fcrek and C. Aykanat,\n                      A fine-grain hypergraph model for 2D decomposition of sparse matrices\n                      , in Proceedings of the 15th International Parallel and Distributed Processing Symposium (IPDPS), San Francisco, CA, 2001."},{"key":"R12","doi-asserted-by":"crossref","unstructured":"U. V. \u00c7ataly\u00fcrek and C. Aykanat,\n                      A hypergraph-partitioning approach for coarse-grain decomposition\n                      , in ACM\/IEEE SC2001, Denver, CO, 2001.","DOI":"10.1145\/582034.582062"},{"key":"R13","unstructured":"C. Chang, T. Kurc, A. Sussman, U. V. \u00c7ataly\u00fcrek, and J. Saltz,\n                      A hypergraph-based workload partitioning strategy for parallel data aggregation\n                      , in Proceedings of the Eleventh SIAM Conference on Parallel Processing for Scientific Computing, SIAM, 2001."},{"key":"R14","unstructured":"T. H. Cormen, C. E. Leiserson, and R. L. Rivest,\n                      Introduction to Algorithms\n                      , MIT Press, McGraw-Hill, New York, 1990."},{"key":"R15","unstructured":"T. Davis,\n                      The University of Florida Sparse Matrix Collection\n                      , Technical report REP-2007-298, CISE Department, University of Florida, Gainesville, FL, 2007."},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1007\/s101070100263"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626499000190"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"B. Hendrickson,\n                      Graph Partitioning and Parallel Solvers: Has the Emperor No Clothes?\n                      , Lecture Notes in Comput. Sci. 1457, Springer-Verlag, New York, 1998, pp. 218\u2013225.","DOI":"10.1007\/BFb0018541"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(00)00048-X"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827598341475"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1142\/S0129053395000051"},{"key":"R23","unstructured":"B. Hendrickson, R. Leland, and R. Van Driessche,\n                      Skewed graph partitioning\n                      , in Proceedings of the Eighth SIAM Conference on Parallel Processing for Scientific Computation, 1997."},{"key":"R24","doi-asserted-by":"crossref","unstructured":"M. Jacunski, P. Sadayappan, and D. K. Panda,\n                      All-to-all broadcast on switch-based clusters of workstations\n                      , in Proceedings of the 13th International Symposium on Parallel Processing and the 10th Symposium on Parallel and Distributed Processing, IPPS'99\/SPDP'99, Washington, DC, 1999, IEEE Computer Society, pp. 325\u2013329.","DOI":"10.1109\/IPPS.1999.760495"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1109\/M-PDT.1995.414844"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"G. Karypis and V. Kumar,\n                      Multilevel Algorithms for Multi-constraint Graph Partitioning\n                      , Technical report 98-019, University of Minnesota, Department of Computer Science\/Army HPC Research Center, Minneapolis, MN, 1998.","DOI":"10.1109\/SC.1998.10018"},{"key":"R28","unstructured":"G. Karypis, V. Kumar, R. Aggarwal, and S. Shekhar,\n                      hMeTiS: A Hypergraph Partitioning Package Version\n                      1.5.3, University of Minnesota, Department of Comp. Sci. and Eng., Army HPC Research Center, Minneapolis, 1998."},{"key":"R29","doi-asserted-by":"crossref","unstructured":"S. Krishnamoorthy, U. Catalyurek, J. Nieplocha, A. Rountev, and P. Sadayappan,\n                      Hypergraph partitioning for automatic memory hierarchy management\n                      , in SC'06: Proceedings of the 2006 ACM\/IEEE Conference on Supercomputing, 206, Tampa, FL, 98 (in cdrom).","DOI":"10.1145\/1188455.1188558"},{"key":"R30","unstructured":"V. Kumar, A. Grama, A. Gupta, and G. Karypis,\n                      Introduction to Parallel Computing: Design and Analysis of Algorithms\n                      , Benjamin\/Cummings, Redwood City, CA, 1994."},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008169609963"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(95)00006-A"},{"key":"R33","doi-asserted-by":"crossref","unstructured":"T. Lengauer,\n                      Combinatorial Algorithms for Integrated Circuit Layout\n                      , Willey\u2013Teubner, Chichester, U.K., 1990.","DOI":"10.1007\/978-3-322-92106-2"},{"key":"R34","doi-asserted-by":"crossref","unstructured":"J. G. Lewis, D. G. Payne, and R. A. van de Geijn,\n                      Matrix-vector multiplication and conjugate gradient algorithms on distributed memory computers\n                      , in Proceedings of the Scalable High Performance Computing Conference, 1994, IEEE, Knoxville, TN, pp. 542\u2013550.","DOI":"10.1109\/SHPCC.1994.296689"},{"key":"R35","doi-asserted-by":"crossref","unstructured":"J. G. Lewis and R. A. van de Geijn,\n                      Distributed memory matrix-vector multiplication and conjugate gradient algorithms\n                      , in Proceedings of Supercomputing'93, Portland, OR, 1993, pp. 484\u2013492.","DOI":"10.1145\/169627.169788"},{"key":"R36","doi-asserted-by":"crossref","unstructured":"F. Manne and T. S\u00f8revik,\n                      Partitioning an array onto a mesh of processors\n                      , in PARA '96: Proceedings of the Third International Workshop on Applied Parallel Computing, Industrial Computation and Optimization, London, UK, 1996, also in Applied Parallel Computing Industrial Computation and Optimization, Lecture Notes in Comput. Sci, 1184, Springer-Verlag, New York, 1996, pp. 467\u2013477.","DOI":"10.1007\/3-540-62095-8_50"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.4330070404"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1994.1126"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1137\/0914033"},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2004.05.003"},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(94)00087-Q"},{"key":"R42","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(91)90089-R"},{"key":"R43","doi-asserted-by":"crossref","unstructured":"K. Schloegel, G. Karypis, and V. Kumar,\n                      A New Algorithm for Multi-objective Graph Partitioning\n                      , Technical report 99-003, University of Minnesota, Department of Computer Science\/Army HPC Research Center, Minneapolis, MN, 1999.","DOI":"10.1007\/3-540-48311-X_42"},{"key":"R44","doi-asserted-by":"crossref","unstructured":"K. Schloegel, G. Karypis, and V. Kumar,\n                      Parallel multilevel algorithms for multi-constraint graph partitioning\n                      , in Proceedings of the Euro-Par 2000 Parallel Processing, Munich, Germany, Lecture Notes in Comput. Sci. 1900, Springer-Verlag, New York, 2000, pp. 296\u2013300.","DOI":"10.1007\/3-540-44520-X_39"},{"key":"R45","unstructured":"B. U\u00e7ar,\n                      Heuristics for a matrix symmetrization problem\n                      , in PPAM 2007, Lecture Notes in Comput. Sci. 4967, Springer-Verlag, New York, 2008, pp. 717\u2013727."},{"key":"R46","doi-asserted-by":"crossref","unstructured":"B. U\u00e7ar and C. Aykanat,\n                      Minimizing communication cost in fine-grain partitioning of sparse matrices\n                      , in ISCIS 2003, Lecture Notes in Comput. Sci. 2869, Springer-Verlag, New York, 2003, pp. 926\u2013933.","DOI":"10.1007\/978-3-540-39737-3_115"},{"key":"R47","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827502410463"},{"key":"R48","unstructured":"B. U\u00e7ar and C. Aykanat,\n                      A Library for Parallel Sparse Matrix-vector Multiplies\n                      , Technical report BU-CE-0506, Department of Computer Engineering, Bilkent University, Ankara, Turkey, 2005."},{"key":"R49","doi-asserted-by":"publisher","DOI":"10.1137\/040617431"},{"key":"R50","doi-asserted-by":"publisher","DOI":"10.1137\/060662459"},{"key":"R51","unstructured":"B. U\u00e7ar, U. V. \u00c7ataly\u00fcrek, and C. Aykanat,\n                      A matrix partitioning interface to PaToH in MATLAB\n                      , Parallel Comput., to appear."},{"key":"R52","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144502409019"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/080737770","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:50:09Z","timestamp":1787334609000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/080737770"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":52,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/080737770"],"URL":"https:\/\/doi.org\/10.1137\/080737770","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]}}}