{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,4]],"date-time":"2026-10-04T21:25:42Z","timestamp":1791149142107,"version":"4.1.0"},"reference-count":43,"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>We investigate the problem of permuting a sparse rectangular matrix into block-diagonal form. Block-diagonal form of a matrix grants an inherent parallelism for solving the deriving problem, as recently investigated in the context of mathematical programming, LU factorization, and QR factorization. To represent the nonzero structure of a matrix, we propose bipartite graph and hypergraph models that reduce the permutation problem to those of graph partitioning by vertex separator and hypergraph partitioning, respectively. Our experiments on a wide range of matrices, using the state-of-the-art graph and hypergraph partitioning tools MeTiS and PaToH\\@, revealed that the proposed methods yield very effective solutions both in terms of solution quality and runtime.<\/jats:p>","DOI":"10.1137\/s1064827502401953","type":"journal-article","created":{"date-parts":[[2004,6,2]],"date-time":"2004-06-02T21:00:53Z","timestamp":1086210053000},"page":"1860-1879","source":"Crossref","is-referenced-by-count":97,"title":["Permuting Sparse Rectangular Matrices into Block-Diagonal Form"],"prefix":"10.1137","volume":"25","author":[{"given":"Cevdet","family":"Aykanat","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ali","family":"Pinar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"\u00dcmit V.","family":"\u00c7ataly\u00fcrek","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,25]]},"reference":[{"key":"R1","unstructured":"C. Ashcraft and J. W. H. Liu,\n                      A Partition Improvement Algorithm for Generalized Nested Dissection\n                      , Tech. Report BCSTECH\u201094\u2010020, Boeing Computer Services, Seattle, WA, 1994."},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479896308433"},{"key":"R3","doi-asserted-by":"crossref","first-page":"1860","DOI":"10.1137\/S1064827502401953","volume":"25","author":"Aykanat Cevdet","year":"2004","journal-title":"SIAM J. Sci. Comput."},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611971484"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90140-Q"},{"key":"R6","unstructured":"T. N. Bui and C. Jones,\n                      A heuristic for reducing fill\u2010in in sparse matrix factorization\n                      , in Proceedings of the 6th SIAM Conference on Parallel Processing for Scientific Computing, SIAM, Philadelphia, 1993, pp. 445\u2013452."},{"key":"R7","doi-asserted-by":"crossref","unstructured":"U. V. \u00c7ataly\u00fcrek and C. Aykanat,\n                      Decomposing irregularly sparse matrices for parallel matrix\u2010vector multiplications\n                      , in Proceedings of the 3rd International Symposium on Solving Irregularly Structured Problems in Parallel, Irregular\u201896, Lecture Notes in Comput. Sci. 1117, Springer\u2010Verlag, Berlin, 1996, pp. 75\u201386.","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, Version3.0\n                      , Department of Computer Engineering, Bilkent University, Ankara, Turkey, 1999."},{"key":"R10","unstructured":"I. O. Center,\n                      Linear Programming Problems\n                      , ftp:\/\/col.biz.uiowa.edu:pub\/testprob\/lp\/gondzio."},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1287\/opre.8.1.101"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/S0025-5610(97)00009-9"},{"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, IEEE Press, Piscataway, NJ, 1982, pp. 175\u2013181.","DOI":"10.1109\/DAC.1982.1585498"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1137\/0710032"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585159"},{"key":"R16","unstructured":"A. Gupta,\n                      Watson Graph Partitioning Package\n                      , Tech. Report RC 20453, IBM T. J. Watson Research Center, Yorktown Heights, NY, 1996."},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1109\/43.644609"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"B. Hendrickson,\n                      Graph partitioning and parallel solvers: Has the emperor no clothes?\n                      , in Proceedings of the 5th International Symposium on Solving Irregularly Structured Problems in Parallel, Irregular\u201898, Lecture Notes in Comput. Sci. 1457, Springer\u2010Verlag, Berlin, 1998, pp. 218\u2013225.","DOI":"10.1007\/BFb0018541"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(00)00048-X"},{"key":"R20","unstructured":"B. Hendrickson and R. Leland,\n                      A Multilevel Algorithm for Partitioning Graphs\n                      , tech. report, Sandia National Laboratories, Albuquerque, NM, 1993."},{"key":"R21","unstructured":"B. Hendrickson and R. Leland,\n                      The Chaco User\u2019s Guide, Version2.0\n                      , Sandia National Laboratories, Albuquerque, NM, 1995."},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827596300656"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1007\/BF01589413"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"Y. F. Hu, C. M. Maguire, and R. J. Blake,\n                      Ordering unsymmetric matrices into bordered block diagonal form for parallel processing\n                      , in Proceedings of Euro\u2010Par \u201899 Parallel Processing: 5th International Euro\u2010Par Conference, Toulouse, France, 1999, P. Amestoy, P. Berger, M. J. Dayd\u00e9, I. S. Duff, V. Frayss\u00e9, L. Giraud, and D. Ruiz, eds., Lecture Notes in Comput. Sci. 1685, Springer\u2010Verlag, Berlin, 1999, pp. 295\u2013302.","DOI":"10.1007\/3-540-48311-X_38"},{"key":"R25","unstructured":"Hungarian Academy of Sciences: Computer and Automation Research Institute, LP Test Sets\n                      , ftp:\/\/ftp.sztaki.hu\/pub\/oplab\/LPTESTSET\/."},{"key":"R26","unstructured":"IMSL User\u2019s Manual, Edition9.2 (International Mathematical and Statistical Library)\n                      , Houston, TX, 1984."},{"key":"R27","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 Version3.0\n                      , Department of Computer Science and Engineering\/Army HPC Research Center, University of Minnesota, Minneapolis, MN, 1998."},{"key":"R28","doi-asserted-by":"crossref","unstructured":"G. Karypis and V. Kumar,\n                      Multilevel Algorithms for Multi\u2010constraint Graph Partitioning\n                      , Tech. Report 98\u2010019, Department of Computer Science\/Army HPC Research Center, University of Minnesota, Minneapolis, MN, 1998.","DOI":"10.1109\/SC.1998.10018"},{"key":"R29","unstructured":"G. Karypis, V. Kumar, R. Aggarwal, and S. Shekhar,\n                      hMeTiS. A Hypergraph Partitioning Package Version1.0.1\n                      , Department of Computer Science and Engineering\/Army HPC Research Center, University of Minnesota, Minneapolis, MN, 1998."},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1970.tb01770.x"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1016\/0025-5610(94)00067-4"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-322-92106-2"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1137\/0910069"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1007\/BF02023050"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1007\/BF01581138"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623496313635"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(92)90046-6"},{"key":"R38","doi-asserted-by":"crossref","unstructured":"A. Pinar, U. V. \u00c7ataly\u00fcrek, C. Aykanat, and M. Pinar,\n                      Decomposing linear programs for parallel solution\n                      , in Proceedings of the Second International Workshop on Applied Parallel Computing, PARA \u201895, Lyngby, Denmark, 1995, Lecture Notes in Comput. Sci. 1041, Springer\u2010Verlag, Berlin, 1996, pp. 473\u2013482.","DOI":"10.1007\/3-540-60902-4_50"},{"key":"R39","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 the Third International Workshop on Applied Parallel Computing, PARA\u201896, Lecture Notes in Comput. Sci. 1184, Springer\u2010Verlag, Berlin, 1997, pp. 592\u2013601.","DOI":"10.1007\/3-540-62095-8_64"},{"key":"R40","unstructured":"A. Pinar and B. Hendrickson,\n                      Partitioning for complex objectives\n                      , in Proceedings of the 15th International Parallel and Distributed Processing Symposium (IPDPS), San Francisco, CA, IEEE Computer Society Press, Los Alamitos, CA, 2001."},{"key":"R41","unstructured":"T. Rashid and T. A. Davis,\n                      An approach for parallelizing any general unsymmetric sparse matrix algorithm\n                      , in Proceedings of the 7th SIAM Conference on Parallel Processing for Scientific Computing, SIAM, Philadelphia, 1995, pp. 413\u2013417."},{"key":"R42","first-page":"199","volume":"12","author":"Stern J.","year":"1993","journal-title":"Mat. Apl. Comput."},{"key":"R43","unstructured":"R. J. Vanderbei,\n                      LOQO User\u2019s Manual, Version4.01\n                      , Tech. Report SOR 97\u201008, Princeton University, Princeton, NJ, 1997."}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S1064827502401953","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:49:21Z","timestamp":1787334561000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S1064827502401953"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,1]]},"references-count":43,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2004,1]]}},"alternative-id":["10.1137\/S1064827502401953"],"URL":"https:\/\/doi.org\/10.1137\/s1064827502401953","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,1]]}}}