{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,21]],"date-time":"2026-09-21T20:13:59Z","timestamp":1790021639052,"version":"4.0.1"},"reference-count":64,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2007,1]]},"abstract":"<jats:p>This paper addresses the parallelization of the preconditioned iterative methods that use explicit preconditioners such as approximate inverses. Parallelizing a full step of these methods requires the coefficient and preconditioner matrices to be well partitioned. We first show that different methods impose different partitioning requirements for the matrices. Then we develop hypergraph models to meet those requirements. In particular, we develop models that enable us to obtain partitionings on the coefficient and preconditioner matrices simultaneously. Experiments on a set of unsymmetric sparse matrices show that the proposed models yield effective partitioning results. A parallel implementation of the right preconditioned BiCGStab method on a PC cluster verifies that the theoretical gains obtained by the models hold in practice.<\/jats:p>","DOI":"10.1137\/040617431","type":"journal-article","created":{"date-parts":[[2007,8,1]],"date-time":"2007-08-01T18:00:32Z","timestamp":1185991232000},"page":"1683-1709","source":"Crossref","is-referenced-by-count":25,"title":["Partitioning Sparse Matrices for Parallel Preconditioned Iterative Methods"],"prefix":"10.1137","volume":"29","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,8,1]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"C. Ababei, N. Selvakkumaran, K. Bazargan, and G. Karypis,\n                      Multi-objective circuit partitioning for cutsize and path-based delay minimization\n                      , in Proceedings of the 2002 IEEE\/ACM International Conference on Computer-aided Design (ICCAD '02), San Jose, CA, 2002, pp. 181\u2013185.","DOI":"10.1145\/774572.774599"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827502401953"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"R. Barrett, M. W. Berry, T. F. Chan, J. Demmel, J. Donato, J. Dongarra, V. Eijkhout, R. Pozo, C. Romine, and H. A. Van Der Vorst,\n                      Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods\n                      , SIAM, Philadelphia, 1994.","DOI":"10.1137\/1.9781611971538"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1006\/jcph.2002.7176"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827599356900"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827599361308"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827594271421"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595294691"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-9274(98)00118-4"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-9274(01)00116-7"},{"key":"R11","unstructured":"M. Benzi and M. T\u016fma,\n                      Private communication\n                      , 2003."},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1099-1506(200004\/05)7:3<99::AID-NLA188>3.0.CO;2-5"},{"key":"R13","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":"R14","doi-asserted-by":"publisher","DOI":"10.1016\/S0045-7825(99)00235-2"},{"key":"R15","unstructured":"G. Burns, R. Daoud, and J. Vaigl,\n                      LAM: An open cluster environment for MPI\n                      , in Proceedings of Supercomputing Symposium '94, J. W. Ross, ed., University of Toronto, 1994, pp. 379\u2013386."},{"key":"R16","unstructured":"\u00dc. 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":"R17","doi-asserted-by":"crossref","unstructured":"\u00dc. V. \u00c7ataly\u00fcrek and C. Aykanat,\n                      Decomposing irregularly sparse matrices for parallel matrix-vector multiplications\n                      , in Parallel Algorithms for Irregularly Structured Problems, Lecture Notes in Comput. Sci. 1117, Springer, Berlin, 1996, pp. 75\u201386.","DOI":"10.1007\/BFb0030098"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1109\/71.780863"},{"key":"R19","unstructured":"\u00dc. V. \u00c7ataly\u00fcrek and C. Aykanat,\n                      PaToH: A Multilevel Hypergraph Partitioning Tool\n                      , Version 3.0, Tech. Report BU-CE-9915, Computer Engineering Department, Bilkent University, Ankara, Turkey, 1999."},{"key":"R20","doi-asserted-by":"crossref","unstructured":"\u00dc. V. \u00c7ataly\u00fcrek and C. Aykanat,\n                      A hypergraph-partitioning approach for coarse-grain decomposition\n                      , in Proceedings of Scientific Computing 2001 (SC2001), Denver, CO, 2001, pp. 10\u201316.","DOI":"10.1145\/582034.582062"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827596311554"},{"key":"R22","unstructured":"C. Chang, T. Kurc, A. Sussman, \u00dc. V. \u00c7ataly\u00fcrek, and J. Saltz,\n                      A hypergraph-based workload partitioning strategy for parallel data aggregation\n                      , in Proceedings of the Tenth SIAM Conference on Parallel Processing for Scientific Computing, Portsmouth, VA, CD-ROM, SIAM, Philadelphia, 2001."},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1137\/S106482759833913X"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1177\/109434200101500106"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827594270415"},{"key":"R26","doi-asserted-by":"crossref","unstructured":"J. K. Cullum, K. Johnson, and M. T23 uma,\n                      Effects of problem decomposition on the convergence behavior of parallel numerical algorithms\n                      , Numer. Linear Algebra Appl., 10 (2003), pp. 445\u2013465.","DOI":"10.1002\/nla.323"},{"key":"R27","unstructured":"T. Davis,\n                      University of Florida Sparse Matrix Collection\n                      , http:\/\/www.cise.ufl.edu\/research\/sparse\/matrices\/."},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1137\/0914029"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"R. W. Freund and N. M. Nachtigal,\n                      A New Krylov-Subspace Method for Symmetric Indefinite Linear Systems\n                      , Tech. Report ORNL\/TM-12754, Oak Ridge National Laboratories, 1994.","DOI":"10.2172\/10190810"},{"key":"R30","unstructured":"G. H. Golub and C. F. Van Loan,\n                      Matrix Computations\n                      , 3rd ed., Johns Hopkins University Press, Baltimore, MD, 1996."},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595288425"},{"key":"R32","unstructured":"M. J. Grote,\n                      SPAI: SParse Approximate Inverse Preconditioner\n                      , http:\/\/www.sam.math.ethz.ch\/$\\!_{^{\\sim}}\\!$grote\/spai\/."},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827594276552"},{"key":"R34","doi-asserted-by":"crossref","unstructured":"B. Hendrickson,\n                      Graph partitioning and parallel solvers: Has the emperor no clothes?\n                      , in Workshop on Parallel Algorithms for Irregularly Structured Problems, Lecture Notes in Comput. Sci. 1457, Springer, Berlin, 1998, pp. 218\u2013225.","DOI":"10.1007\/BFb0018541"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1016\/S0045-7825(99)00241-8"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(00)00048-X"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827598341475"},{"key":"R38","unstructured":"C. Hoover, A. DeGroot, J. Maltby, and R. Procassini,\n                      Paradyn: Dyna3d for Massively Parallel Computers\n                      , Presentation at Tri-Laboratory Engineering Conference on Computational Modeling, Pleasanton, CA, 1995."},{"key":"R39","unstructured":"T. Huckle,\n                      Approximate Sparsity Patterns for the Inverse of a Matrix and Preconditioning\n                      , Tech. Report 342\/12\/98 A, Technische Universit\u00e4t M\u00fcnchen, Germany, 1998."},{"key":"R40","doi-asserted-by":"crossref","unstructured":"G. Karypis,\n                      Multi-constraint Mesh Partitioning for Contact\/Impact Computations\n                      , Tech. Report 03-022, Department of Computer Science and Engineering\/Army HPC Research Center, University of Minnesota, Minneapolis, MN, 2003.","DOI":"10.21236\/ADA439573"},{"key":"R41","doi-asserted-by":"crossref","unstructured":"G. Karypis and V. Kumar,\n                      Multilevel Algorithms for Multi-constraint Graph Partitioning\n                      , Tech. Report 98-019, Department of Computer Science\/Army HPC Research Center, University of Minnesota, Minneapolis, MN, 1998.","DOI":"10.1109\/SC.1998.10018"},{"key":"R42","unstructured":"G. Karypis and V. Kumar,\n                      Multilevel Algorithms for Multi-constraint Hypergraph Partitioning\n                      , Tech. Report 99-034, Department of Computer Science\/Army HPC Research Center, University of Minnesota, Minneapolis, MN, 1998."},{"key":"R43","doi-asserted-by":"crossref","unstructured":"T. G. Kolda,\n                      Partitioning sparse rectangular matrices for parallel processing\n                      , in Solving Irregularly Structured Problems in Parallel, Lecture Notes in Comput. Sci. 1457, Springer, Berlin, 1998, pp. 68\u201379.","DOI":"10.1007\/BFb0018528"},{"key":"R44","doi-asserted-by":"publisher","DOI":"10.1137\/0614004"},{"key":"R45","doi-asserted-by":"publisher","DOI":"10.1142\/S0129053395000117"},{"key":"R46","doi-asserted-by":"crossref","unstructured":"T. Lengauer,\n                      Combinatorial Algorithms for Integrated Circuit Layout\n                      , Wiley\u2013Teubner, Chichester, UK, 1990.","DOI":"10.1007\/978-3-322-92106-2"},{"key":"R47","doi-asserted-by":"publisher","DOI":"10.1177\/109434200001400203"},{"key":"R48","unstructured":"G. Meurant,\n                      Computer Solution of Large Linear Systems\n                      , Elsevier, Amsterdam, The Netherlands, 1999."},{"key":"R49","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 in Physics, Chemistry and Engineering Science, Lecture Notes in Comput. Sci. 1041, Springer, Berlin, 1996, pp. 473\u2013482.","DOI":"10.1007\/3-540-60902-4_50"},{"key":"R50","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1998.1433"},{"key":"R51","doi-asserted-by":"crossref","unstructured":"S. Plimpton, B. Hendrickson, and J. Stewart,\n                      A parallel rendezvous algorithm for interpolation between multiple grids\n                      , in Proceedings of the 1998 ACM\/IEEE Conference on Supercomputing, San Jose, CA, 1998, CD-ROM, pp. 1\u20138.","DOI":"10.1109\/SC.1998.10032"},{"key":"R52","unstructured":"Y. Saad,\n                      Iterative Methods for Sparse Linear Systems\n                      , PWS Publishing, Boston, MA, 1996."},{"key":"R53","doi-asserted-by":"crossref","unstructured":"K. Schloegel, G. Karypis, and V. Kumar,\n                      A New Algorithm for Multi-objective Graph Partitioning\n                      , Tech. Report 99-033, Department of Computer Science and Engineering, University of Minnesota, Minneapolis, MN, 1999.","DOI":"10.1007\/3-540-48311-X_42"},{"key":"R54","unstructured":"K. Schloegel, G. Karypis, and V. Kumar,\n                      Graph partitioning for high-performance scientific simulations\n                      , in CRPC Parallel Computing Handbook, J. Dongarra, I. Foster, G. Fox, W. Gropp, K. Kennedy, L. Torczon, and A. White, eds., Morgan Kaufmann, San Francisco, CA, 2002, Chap. 18, pp. 491\u2013541."},{"key":"R55","doi-asserted-by":"crossref","unstructured":"N. Selvakkumaran and G. Karypis,\n                      Multi-objective hypergraph partitioning algorithms for cut and maximum subdomain degree minimization\n                      , in Proceedings of the 2003 IEEE\/ACM International Conference on Computer-Aided Design (ICCAD '03), San Jose, CA, 2003, pp. 726\u2013733.","DOI":"10.1109\/ICCAD.2003.159757"},{"key":"R56","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":"R57","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1096-9128(199803)10:3<229::AID-CPE296>3.0.CO;2-I"},{"key":"R58","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 the 18th International Symposium on Computer and Information Sciences (ISCIS XVIII), A. Yaz\u0131c\u0131 and C. \u015eener, eds., Antalya, Turkey, 2003.","DOI":"10.1007\/978-3-540-39737-3_115"},{"key":"R59","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827502410463"},{"key":"R60","unstructured":"B. U\u00e7ar and C. Aykanat,\n                      Experiments on Hypergraph Models for Parallelizing Preconditioned Iterative Methods\n                      , Tech. Report BU-CE-0413, Department of Computer Engineering, Bilkent University, Ankara, Turkey, 2004."},{"key":"R61","unstructured":"B. U\u00e7ar and C. Aykanat,\n                      A Library for Parallel Sparse Matrix-Vector Multiplies\n                      , Tech. Report BU-CE-0506, Department of Computer Engineering, Bilkent University, Ankara, Turkey, 2005."},{"key":"R62","doi-asserted-by":"publisher","DOI":"10.1137\/0913035"},{"key":"R63","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144502409019"},{"key":"R64","doi-asserted-by":"publisher","DOI":"10.1016\/S0307-904X(00)00041-X"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/040617431","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:58:31Z","timestamp":1787335111000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/040617431"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,1]]},"references-count":64,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2007,1]]}},"alternative-id":["10.1137\/040617431"],"URL":"https:\/\/doi.org\/10.1137\/040617431","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,1]]}}}