{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,4]],"date-time":"2026-10-04T21:25:43Z","timestamp":1791149143946,"version":"4.1.0"},"reference-count":40,"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":[[2004,1]]},"abstract":"<jats:p>This paper addresses the problem of one-dimensional partitioning of structurally unsymmetric square and rectangular sparse matrices for parallel matrix-vector and matrix-transpose-vector multiplies. The objectiveis to minimize the communication cost while maintaining the balance on computational loads of processors. Most of the existing partitioning models consider only the total message volume hoping that minimizing this communication-cost metric is likely to reduce other metrics. However, the total message latency (start-up time) may be more important than the total message volume. Furthermore, the maximum message volume and latency handled by a single processor are also important metrics. We propose a two-phase approach that encapsulates all these four communication-cost metrics. The objective in the first phase is to minimize the total message volume while maintaining the computational-load balance. The objective in the second phase is to encapsulate the remaining three communication-cost metrics. We propose communication-hypergraph and partitioning models for the second phase. We then present several methods for partitioning communication hypergraphs. Experiments on a wide range of test matrices show that the proposed approach yields very effective partitioning results. A parallel implementation on a PC cluster verifies that the theoretical improvements shown by partitioning results hold in practice.<\/jats:p>","DOI":"10.1137\/s1064827502410463","type":"journal-article","created":{"date-parts":[[2004,6,2]],"date-time":"2004-06-02T21:00:53Z","timestamp":1086210053000},"page":"1837-1859","source":"Crossref","is-referenced-by-count":59,"title":["Encapsulating Multiple Communication-Cost Metrics in Partitioning Sparse Rectangular Matrices for Parallel Matrix-Vector Multiplies"],"prefix":"10.1137","volume":"25","author":[{"given":"Bora","family":"U\u00e7ar","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Cevdet","family":"Aykanat","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,25]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1109\/43.828555"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827502401953"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1006\/jcph.2002.7176"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-9274(98)00118-4"},{"key":"R5","unstructured":"G. Burns, R. Daoud, and J. Vaigl,\n                      LAM: An open cluster environment for MPI\n                      , in Proceedings of Supercomputing Symposium \u201894, J. W. Ross, ed., University of Toronto, Ontario, Canada, 1994, pp. 379\u2013386."},{"key":"R6","unstructured":"U. V. \u00c7ataly\u00fcrek,\n                      Hypergraph Models for Sparse Matrix Partitioning and Reordering\n                      , Ph.D. thesis, Computer Engineering and Information Science, Bilkent University, Ankara, Turkey, 1999."},{"key":"R7","doi-asserted-by":"crossref","unstructured":"\u00dcmit \u00c7ataly\u00fcrek, Cevdet Aykanat, Decomposing irregularly sparse matrices for parallel matrix\u2010vector multiplication, Lecture Notes in Comput. Sci., Vol. 1117, Springer, Berlin, 1996, 75\u2013861658073","DOI":"10.1007\/BFb0030098"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1109\/71.780863"},{"key":"R9","unstructured":"U. V. \u00c7ataly\u00fcrek and C. Aykanat,\n                      PaToH: A Multilevel Hypergraph Partitioning Tool, Version\n                      3.0, Tech. rep. BU\u2010CE\u20109915, Computer Engineering Department, Bilkent University, Ankara, Turkey, 1999."},{"key":"R10","doi-asserted-by":"crossref","unstructured":"U. V. \u00c7ataly\u00fcrek and C. Aykanat,\n                      A hypergraph\u2010partitioning approach for coarse\u2010grain decomposition\n                      , in Proceedings of the IEEE Symposium on Scientific Computing, Denver, CO, 2001, pp. 10\u201316.","DOI":"10.1145\/582034.582062"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1109\/43.573831"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1096-9128(199710)9:10<915::AID-CPE277>3.0.CO;2-C"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"C. M. Fiduccia and R. M. Mattheyses,\n                      A linear\u2010time heuristic for improving network partitions\n                      , in Proceedings of the 19th ACM\/IEEE Design Automation Conference, ACM, New York, IEEE Computer Society, Los Alamitos, CA, 1982, pp. 175\u2013181.","DOI":"10.1109\/DAC.1982.1585498"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1007\/BF01385726"},{"key":"R15","unstructured":"G. H. Golub and C. F. V. Loan,\n                      Matrix Computations\n                      , 3rd ed., The Johns Hopkins University Press, Baltimore, 1996."},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827594276552"},{"key":"R17","unstructured":"A. Gupta,\n                      Watson Graph Partitioning Package\n                      , Tech. rep. RC 20453, IBM T. J. Watson Research Center, Yorktown Heights, NY, 1996."},{"key":"R18","unstructured":"M. Hegland,\n                      Description and Use of Animal Breeding Data for Large Least Squares Problems\n                      , Tech. rep. TR\u2010PA\u201093\u201050, CERFACS, Toulouse, France, 1993."},{"key":"R19","doi-asserted-by":"crossref","unstructured":"B. Hendrickson,\n                      Graph partitioning and parallel solvers: Has the emperor no clothes?\n                      , in Solving Irregularly Structured Problems in Parallel, Lecture Notes in Comput. Sci. 1457, Springer\u2010Verlag, Berlin, 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","unstructured":"B. Hendrickson and R. Leland,\n                      The Chaco Users\u2019s Guide, Version\n                      2.0, Tech. rep. SAND95\u20102344, Sandia National Laboratories, Albuquerque, NM, 1995."},{"key":"R23","unstructured":"E. Horowitz and S. Sahni,\n                      Fundamentals of Computer Algorithms\n                      , Computer Science Press, Rockville, MD, 1978."},{"key":"R24","unstructured":"G. Karypis and V. Kumar,\n                      MeTiS: A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes, and Computing Fill\u2010Reducing Orderings of Sparse Matrices Version\n                      3.0, Tech. rep., Department of Computer Science and Engineering, Army HPC Research Center, University of Minnesota, Minneapolis, MN, 1998."},{"key":"R25","doi-asserted-by":"crossref","unstructured":"G. Karypis and V. Kumar,\n                      Multilevel Algorithms for Multi\u2010constraint Graph Partitioning\n                      , Tech. rep. 98\u2010019, Department of Computer Science, Army HPC Research Center, University of Minnesota, Minneapolis, MN, 1998.","DOI":"10.1109\/SC.1998.10018"},{"key":"R26","unstructured":"G. Karypis, V. Kumar, R. Aggarwal, and S. Shekhar,\n                      hMeTiS: A Hypergraph Partitioning Package Version\n                      1.0.1, Department of Computer Science and Engineering, Army HPC Research Center, University of Minnesota, Minneapolis, MN, 1998."},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1970.tb01770.x"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-322-92106-2"},{"key":"R29","unstructured":"H. \u00d6zakta\u015f,\n                      Algorithms for Linear and Convex Feasibility Problems: A Brief Study of Iterative Projection, Localization and Subgradient Methods\n                      , Ph.D. thesis, Industrial Engineering Department, Bilkent University, Ankara, Turkey, 1998."},{"key":"R30","doi-asserted-by":"crossref","unstructured":"H. \u00d6zaktas, M. Akg\u00fcl, and M. \u00c7. Pinar,\n                      A parallel surrogate constraint approach to the linear feasibility problem\n                      , in Applied Parallel Computing: Computations in Physics, Chemistry, and Engineering Science, Lecture Notes in Comput. Sci. 1184, Springer\u2010Verlag, Berlin, 1996, pp. 565\u2013574.","DOI":"10.1007\/3-540-62095-8_61"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1145\/355984.355989"},{"key":"R32","doi-asserted-by":"crossref","unstructured":"A. Pinar, U. V. \u00c7ataly\u00fcrek, C. Aykanat, and M. \u00c7. Pinar,\n                      Decomposing linear programs for parallel solution\n                      , in Proceedings of the 2nd International Workshop on Parallel Computing, Lecture Notes in Comput. Sci. 1041, Springer\u2010Verlag, Berlin, 1996, pp. 473\u2013482.","DOI":"10.1007\/3-540-60902-4_50"},{"key":"R33","unstructured":"A. Pinar and B. Hendrickson,\n                      Graph partitioning for complex objectives\n                      , in Proceedings of Irregular 2001 Eighth International Workshop on Solving Irregularly Structured Problems in Parallel, San Francisco, CA, 2001."},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718003"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1109\/12.8730"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1109\/12.260640"},{"key":"R37","doi-asserted-by":"crossref","unstructured":"K. Schloegel, G. Karypis, and V. Kumar,\n                      A New Algorithm for Multi\u2010Objective Graph Partitioning\n                      , Tech. rep. 99\u2010003, Department of Computer Science, Army HPC Research Center, University of Minnesota, Minneapolis, MN, 1999.","DOI":"10.1007\/3-540-48311-X_42"},{"key":"R38","unstructured":"T. Sterling, D. Savarese, D. J. Becker, J. E. Dorband, U. A. Ranaweke, and C. V. Packer,\n                      BEOWULF: A parallel workstation for scientific computation\n                      , in Proceedings of the 24th International Conference on Parallel Processing, Oconomowoc, WI, 1995, pp. 11\u201334."},{"key":"R39","unstructured":"E. Turna,\n                      Parallel Algorithms for the Solution of Large Sparse Inequality Systems on Distributed Memory Architectures\n                      , Master\u2019s thesis, Computer Engineering and Information Science, Bilkent University, Ankara, Turkey, 1998."},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.1007\/BF00939954"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S1064827502410463","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:49:19Z","timestamp":1787334559000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S1064827502410463"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,1]]},"references-count":40,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2004,1]]}},"alternative-id":["10.1137\/S1064827502410463"],"URL":"https:\/\/doi.org\/10.1137\/s1064827502410463","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,1]]}}}