{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,4]],"date-time":"2026-10-04T21:25:34Z","timestamp":1791149134251,"version":"4.1.0"},"reference-count":13,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM Rev."],"published-print":{"date-parts":[[2007,1]]},"abstract":"<jats:p>We provide an exposition of hypergraph models for parallelizing sparse matrix-vector multiplies. Our aim is to emphasize the expressive power of hypergraph models. First, we set forth an elementary hypergraph model for the parallel matrix-vector multiply based on one-dimensional (1D) matrix partitioning. In the elementary model, the vertices represent the data of a matrix-vector multiply, and the nets encode dependencies among the data. We then apply a recently proposed hypergraph transformation operation to devise models for 1D sparse matrix partitioning. The resulting 1D partitioning models are equivalent to the previously proposed computational hypergraph models and are not meant to be replacements for them. Nevertheless, the new models give us insights into the previous ones and help us explain a subtle requirement, known as the consistency condition, of hypergraph partitioning models. Later, we demonstrate the flexibility of the elementary model on a few 1D partitioning problems that are hard to solve using the previously proposed models. We also discuss extensions of the proposed elementary model to two-dimensional matrix partitioning.<\/jats:p>","DOI":"10.1137\/060662459","type":"journal-article","created":{"date-parts":[[2007,10,26]],"date-time":"2007-10-26T16:33:08Z","timestamp":1193416388000},"page":"595-603","source":"Crossref","is-referenced-by-count":35,"title":["Revisiting Hypergraph Models for Sparse Matrix Partitioning"],"prefix":"10.1137","volume":"49","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":[[2007,11,1]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827502401953"},{"key":"R2","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":"R3","doi-asserted-by":"crossref","unstructured":"\u00dc. V. \u00c7ataly\u00fcrek and C. Aykanat,\n                      Decomposing irregularly sparse matrices for parallel matrix-vector multiplications\n                      , in Proceedings of Parallel Algorithms for Irregularly Structured Problems, Santa Barbara, CA, 1996, Lecture Notes in Comput. Sci. 1117, Springer, Berlin, 1996, pp. 75\u201386.","DOI":"10.1007\/BFb0030098"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1109\/71.780863"},{"key":"R5","unstructured":"\u00dc. V. \u00c7ataly\u00fcrek and C. Aykanat,\n                      PaToH: A Multilevel Hypergraph Partitioning Tool\n                      , Version 3.0, Tech. Rep. BU-CE-9915, Computer Engineering Department, Bilkent University, Ankara, Turkey, 1999."},{"key":"R6","unstructured":"\u00dc. 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, CD-ROM, IEEE, 2001."},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(00)00048-X"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"T. Lengauer,\n                      Combinatorial Algorithms for Integrated Circuit Layout\n                      , Wiley-Teubner, Chichester, UK, 1990.","DOI":"10.1007\/978-3-322-92106-2"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"A. P\u0131nar, \u00dc. V. \u00c7ataly\u00fcrek, C. Aykanat, and M. P\u0131nar,\n                      Decomposing linear programs for parallel solution\n                      , in Proceedings of the Second International Workshop on Applied Parallel Computing, PARA'95 Lyngby, Denmark, 1995, Lecture Notes in Comput. Sci. 1041, Springer, Berlin, 1996, pp. 473\u2013482.","DOI":"10.1007\/3-540-60902-4_50"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"B. U\u00e7ar and C. Aykanat,\n                      Minimizing communication cost in fine-grain partitioning of sparse matrices\n                      , in Proceedings of ISCIS-2003, Antalya, Turkey, 2003, Lecture Notes in Comput. Sci. 2869, Springer, Berlin, 2003, pp. 926\u2013933.","DOI":"10.1007\/978-3-540-39737-3_115"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827502410463"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1137\/040617431"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144502409019"}],"container-title":["SIAM Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/060662459","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,20]],"date-time":"2026-08-20T13:07:21Z","timestamp":1787231241000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/060662459"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,1]]},"references-count":13,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2007,1]]}},"alternative-id":["10.1137\/060662459"],"URL":"https:\/\/doi.org\/10.1137\/060662459","relation":{},"ISSN":["0036-1445","1095-7200"],"issn-type":[{"value":"0036-1445","type":"print"},{"value":"1095-7200","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,1]]}}}