{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,20]],"date-time":"2026-08-20T15:29:11Z","timestamp":1787239751276,"version":"3.56.0"},"reference-count":46,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM Rev."],"published-print":{"date-parts":[[2005,1]]},"abstract":"<jats:p>A new method is presented for distributing data in sparse matrix-vector multiplication. The method is two-dimensional, tries to minimize the true communication volume, and also tries to spread the computation and communication work evenly over the processors. The method starts with a recursive bipartitioning of the sparse matrix, each time splitting a rectangular matrix into two parts with a nearly equal number of nonzeros. The communication volume caused by the split is minimized. After the matrix partitioning, the input and output vectors are partitioned with the objective of minimizing the maximum communication volume per processor. Experimental results of our implementation, Mondriaan, for a set of sparse test matrices show a reduction in communication volume compared to one-dimensional methods, and in general a good balance in the communication work. Experimental timings of an actual parallel sparse matrix-vector multiplication on an SGI Origin 3800 computer show that a sufficiently large reduction in communication volume leads to savings in execution time.<\/jats:p>","DOI":"10.1137\/s0036144502409019","type":"journal-article","created":{"date-parts":[[2005,9,7]],"date-time":"2005-09-07T21:00:16Z","timestamp":1126126816000},"page":"67-95","source":"Crossref","is-referenced-by-count":149,"title":["A Two-Dimensional Data Distribution Method for Parallel Sparse Matrix-Vector Multiplication"],"prefix":"10.1137","volume":"47","author":[{"given":"Brendan","family":"Vastenhouw","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rob H.","family":"Bisseling","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,8,4]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719581"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611971538"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1987.1676942"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144598347035"},{"key":"R5","unstructured":", Proceedings of the Ninth SIAM Conference on Parallel Processing for Scientific Computing 1999, Society for Industrial and Applied Mathematics (SIAM), 1999, 0\u20130, 1 CD\u2010ROM (Windows, Macintosh and UNIX), Held in San Antonio, TX, March 22\u201324, 19992001m:65006"},{"key":"R6","unstructured":"R. Bisseling, Parallel iterative solution of sparse linear systems on a transputer network, Inst. Math. Appl. Conf. Ser. New Ser., Vol. 46, Oxford Univ. Press, New York, 1993, 253\u20132711370943"},{"key":"R7","unstructured":", Information processing \u201994. Vol. I, Proceedings of the IFIP Thirteenth World Computer Congress held in Hamburg, August 28\u2013September 2, 1994, IFIP Transactions A: Computer Science and Technology, A\u201051, North\u2010Holland Publishing Co., 1994, 0\u20130, xxviii+628, Technology and foundations95j:68014"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"R. F. Boisvert, R. Pozo, K. Remington, R. F. Barrett, and J. J. Dongarra,\n                      Matrix Market: A web resource for test matrix collections\n                      , in The Quality of Numerical Software: Assessment and Enhancement, R. F. Boisvert, ed., Chapman and Hall, London, 1997, pp. 125\u2013137.","DOI":"10.1007\/978-1-5041-2940-4_9"},{"key":"R9","unstructured":", Parallel processing for scientific computing. Vol. I, II, Proceedings of the Sixth SIAM Conference held in Norfolk, Virginia, March 22\u201324, 1993, Society for Industrial and Applied Mathematics (SIAM), 1993, 0\u20130, Vol. I: xx+500+Iiv pp.; Vol. II: pp. i\u2013xx, 501\u20131042 and Ii\u2013Iiv93k:65003"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1109\/71.780863"},{"key":"R11","unstructured":"\u00dc. V. \u00c7ataly\u00fcrek and C. Aykanat,\n                      A fine\u2010grain hypergraph model for 2D decomposition of sparse matrices\n                      , in Proceedings of the 8th International Workshop on Solving Irregularly Structured Problems in Parallel, IEEE, Los Alamitos, CA, 2001, p. 118."},{"key":"R12","doi-asserted-by":"crossref","unstructured":"\u00dc. V. \u00c7ataly\u00fcrek and C. Aykanat,\n                      A hypergraph\u2010partitioning approach for coarse\u2010grain decomposition\n                      , in Proceedings of Supercomputing 2001, ACM, New York, 2001, p. 42.","DOI":"10.1145\/582034.582062"},{"key":"R13","unstructured":"T. A. Davis,\n                      University of Florida Sparse Matrix Collection\n                      , http:\/\/www.cise.ufl.edu\/ research\/sparse\/matrices, 1994\u20132003."},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1145\/62038.62043"},{"key":"R15","unstructured":"I. S. Duff, R. G. Grimes, and J. G. Lewis,\n                      The Rutherford\u2013Boeing Sparse Matrix Collection\n                      , Technical Report TR\/PA\/97\/36, CERFACS, Toulouse, France, 1997."},{"key":"R16","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 Design Automation Conference, IEEE, Los Alamitos, CA, 1982, pp. 175\u2013181.","DOI":"10.1109\/DAC.1982.1585498"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"R. Fletcher,\n                      Conjugate gradient methods for indefinite systems\n                      , in Proceedings of the Dundee Biennial Conference on Numerical Analysis, G. A. Watson, ed., Lecture Notes in Math. 506, Springer\u2010Verlag, Berlin, 1976, pp. 73\u201389.","DOI":"10.1007\/BFb0080116"},{"key":"R18","unstructured":"G. C. Fox, M. A. Johnson, G. A. Lyzenga, S. W. Otto, J. K. Salmon, and D. W. Walker,\n                      Solving Problems on Concurrent Processors: Vol. I, General Techniques and Regular Problems\n                      , Prentice\u2010Hall, Englewood Cliffs, NJ, 1988."},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1007\/BF01385726"},{"key":"R20","first-page":"10","volume":"13","author":"Gay D. M.","year":"1985","journal-title":"MPS COAL Newsletter"},{"key":"R21","volume-title":"Matrix computations","author":"Golub Gene","year":"1996"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0018521"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(00)00048-X"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827598341475"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"B. Hendrickson and R. Leland,\n                      A multilevel algorithm for partitioning graphs\n                      , in Proceedings of Supercomputing 1995, ACM, New York, 1995.","DOI":"10.1145\/224170.224228"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1142\/S0129053395000051"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.6028\/jres.049.044"},{"key":"R28","unstructured":"J. M. D. Hill, S. R. Donaldson, and A. McEwan,\n                      Installation and User Guide for the Oxford BSP Toolset (v1.4) Implementation of BSPlib\n                      , Technical Report, Oxford University Computing Laboratory, Oxford, UK, 1998."},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(98)00093-3"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1016\/S0098-1354(99)00314-2"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144598334138"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1970.tb01770.x"},{"key":"R34","unstructured":"J. H. H. Koster,\n                      Parallel Templates for Numerical Linear Algebra: A High\u2010Performance Computation Library\n                      , Master\u2019s thesis, Mathematical Institute, Utrecht University, Utrecht, The Netherlands, 2002."},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-322-92106-2"},{"key":"R36","doi-asserted-by":"crossref","unstructured":"J. G. Lewis and R. A. van de Geijn,\n                      Distributed memory matrix\u2010vector multiplication and conjugate gradient algorithms\n                      , in Proceedings of Supercomputing 1993, ACM, New York, 1993, pp. 484\u2013492.","DOI":"10.1145\/169627.169788"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1137\/0914033"},{"key":"R38","doi-asserted-by":"crossref","unstructured":"A. Pinar and C. Aykanat,\n                      An effective model to decompose linear programs for parallel solution\n                      , in Proceedings of PARA \u201996, J. Wa\u015bniewski, J. Dongarra, K. Madsen, and D. Olesen, eds., Lecture Notes in Comput. Sci. 1184, Springer\u2010Verlag, Berlin, 1997, pp. 592\u2013601.","DOI":"10.1007\/3-540-62095-8_64"},{"key":"R39","doi-asserted-by":"crossref","unstructured":"A. Pinar and C. Aykanat,\n                      Sparse matrix decomposition with optimal load balancing\n                      , in Proceedings of the International Conference on High Performance Computing, IEEE, 1997, pp. 224\u2013229.","DOI":"10.1109\/HIPC.1997.634497"},{"key":"R40","doi-asserted-by":"crossref","unstructured":"A. Pinar, \u00dc. V. \u00c7ataly\u00fcrek, C. Aykanat, and M. Pinar,\n                      Decomposing linear programs for parallel solution\n                      , in Proceedings of PARA \u201995, J. Dongarra, K. Madsen, and J. Wa\u015bniewski, eds., Lecture Notes in Comput. Sci. 1041, Springer\u2010Verlag, Berlin, 1996, pp. 473\u2013482.","DOI":"10.1007\/3-540-60902-4_50"},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(94)00087-Q"},{"key":"R42","doi-asserted-by":"publisher","DOI":"10.1137\/0907058"},{"key":"R43","doi-asserted-by":"publisher","DOI":"10.1137\/0913035"},{"key":"R44","doi-asserted-by":"publisher","DOI":"10.1006\/jcph.2002.7095"},{"key":"R45","unstructured":"B. Vastenhouw,\n                      A Parallel Web Search Engine Based on Latent Semantic Indexing\n                      , Master\u2019s thesis, Mathematical Institute, Utrecht University, Utrecht, The Netherlands, 2001."},{"key":"R46","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-739X(00)00107-2"}],"container-title":["SIAM Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0036144502409019","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,20]],"date-time":"2026-08-20T14:50:35Z","timestamp":1787237435000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0036144502409019"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,1]]},"references-count":46,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2005,1]]}},"alternative-id":["10.1137\/S0036144502409019"],"URL":"https:\/\/doi.org\/10.1137\/s0036144502409019","relation":{},"ISSN":["0036-1445","1095-7200"],"issn-type":[{"value":"0036-1445","type":"print"},{"value":"1095-7200","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,1]]}}}