{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,21]],"date-time":"2026-09-21T08:42:35Z","timestamp":1789980155179,"version":"4.0.1"},"reference-count":21,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2013,1]]},"abstract":"<jats:p>We investigate the problem of symmetrically permuting a square sparse matrix into a block diagonal form with overlap. This permutation problem arises in the parallelization of an explicit formulation of the multiplicative Schwarz preconditioner and a more recent block overlapping banded linear solver as well as its application to general sparse linear systems. In order to formulate this permutation problem as a graph theoretical problem, we define a constrained version of the multiway graph partitioning by vertex separator (GPVS) problem, which is referred to as the ordered GPVS (oGPVS) problem. However, existing graph partitioning tools are unable to solve the oGPVS problem. So, we also show how the recursive bipartitioning framework can be utilized for solving the oGPVS problem. For this purpose, we propose a left-to-right bipartitioning approach together with a novel vertex fixation scheme so that existing 2-way GPVS tools that support fixed vertices can be effectively and efficiently utilized in the recursive bipartitioning framework. Experimental results on a wide range of matrices confirm the validity of the proposed approach.<\/jats:p>","DOI":"10.1137\/120861242","type":"journal-article","created":{"date-parts":[[2013,2,12]],"date-time":"2013-02-12T12:40:21Z","timestamp":1360672821000},"page":"C99-C121","source":"Crossref","is-referenced-by-count":7,"title":["A Recursive Bipartitioning Algorithm for Permuting Sparse Square Matrices into Block Diagonal Form with Overlap"],"prefix":"10.1137","volume":"35","author":[{"given":"Seher","family":"Acer","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Enver","family":"Kayaaslan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Cevdet","family":"Aykanat","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2013,2,12]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2006.05.005"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827502401953"},{"key":"atypb3","volume-title":"Sandia National Laboratories","author":"Boman E.","year":"2007"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1109\/71.780863"},{"key":"atypb5","volume-title":"Version 3.0","author":"\u00c7ataly\u00fcrek \u00dc. V.","year":"1999"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1137\/090757575"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2009.04.011"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2010.119"},{"key":"atypb9","unstructured":"T. Davis,\n                      The University of Florida Sparse Matrix Collection\n                      , Tech. Report REP-2007-298, CISE Department, University of Florida, Gainesville, FL, 2007."},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1007\/BF01582130"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1145\/355841.355845"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2008.01.004"},{"key":"atypb13","volume-title":"Proceedings of the 17th IMACS World Congress: Scientific Computation, Applied Mathematics and Simulation","author":"Kahou G. A. A.","year":"2005"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1016\/j.apnum.2007.01.009"},{"key":"atypb15","volume-title":"Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices, Version 4.0, Department of Comp. Sci. and Eng.","author":"Karypis G.","year":"1998"},{"key":"atypb16","volume-title":"Version 1.0.1, Department of Comp. Sci. and Eng.","author":"Karypis G.","year":"1998"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1145\/66888.66890"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/j.cam.2010.04.016"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1016\/j.cam.2008.08.019"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2004.05.003"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1145\/98267.98287"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/120861242","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:50:29Z","timestamp":1787327429000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/120861242"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["10.1137\/120861242"],"URL":"https:\/\/doi.org\/10.1137\/120861242","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1]]}}}