{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,5]],"date-time":"2026-03-05T10:55:21Z","timestamp":1772708121123,"version":"3.50.1"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2022,8,31]],"date-time":"2022-08-31T00:00:00Z","timestamp":1661904000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF-1919021"],"award-info":[{"award-number":["CCF-1919021"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2022,12,31]]},"abstract":"<jats:p>Even distribution of irregular workload to processing units is crucial for efficient parallelization in many applications. In this work, we are concerned with a spatial partitioning called rectilinear partitioning (also known as generalized block distribution). More specifically, we address the problem of symmetric rectilinear partitioning of two dimensional domains, and utilize sparse matrices to model them. By symmetric, we mean both dimensions (i.e., the rows and columns of the matrix) are identically partitioned yielding a tiling where the diagonal tiles (blocks) will be squares. We first show that the optimal solution to this problem is NP-hard, and we propose four heuristics to solve two different variants of this problem. To make the proposed techniques more applicable in real life application scenarios, we further reduce their computational complexities by utilizing effective sparsification strategies together with an efficient sparse prefix-sum data structure. We experimentally show the proposed algorithms are efficient and effective on more than six hundred test matrices\/graphs.<\/jats:p>","DOI":"10.1145\/3523750","type":"journal-article","created":{"date-parts":[[2022,8,31]],"date-time":"2022-08-31T11:39:42Z","timestamp":1661945982000},"page":"1-26","source":"Crossref","is-referenced-by-count":3,"title":["On Symmetric Rectilinear Partitioning"],"prefix":"10.1145","volume":"27","author":[{"given":"Abdurrahman","family":"Ya\u015far","sequence":"first","affiliation":[{"name":"School of Computational Science and Engineering, Georgia Institute of Technology, Atlanta, GA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Muhammed Fati\u0307h","family":"Balin","sequence":"additional","affiliation":[{"name":"School of Computational Science and Engineering, Georgia Institute of Technology, Atlanta, GA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaojing","family":"An","sequence":"additional","affiliation":[{"name":"School of Computational Science and Engineering, Georgia Institute of Technology, Atlanta, GA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kaan","family":"Sancak","sequence":"additional","affiliation":[{"name":"School of Computational Science and Engineering, Georgia Institute of Technology, Atlanta, GA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"\u00dcmit V.","family":"\u00c7ataly\u00fcrek","sequence":"additional","affiliation":[{"name":"School of Computational Science and Engineering, Georgia Institute of Technology, Atlanta, GA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,8,31]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.20"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1987.1676942"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/2503210.2503293"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/71.780863"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1137\/080737770"},{"issue":"1","key":"e_1_3_2_7_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2049662.2049663","article-title":"The University of Florida sparse matrix collection","volume":"38","author":"Davis Timothy A.","year":"2011","unstructured":"Timothy A. Davis and Yifan Hu. 2011. The University of Florida sparse matrix collection. ACM Transactions on Mathematical Software 38, 1 (2011), 1.","journal-title":"ACM Transactions on Mathematical Software"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492916000076"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/3434393"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/s101070100263"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/12130.12142"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1093\/nsr\/nwt032"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380240306"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/2866577"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.5555\/574824"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.5555\/646010.676857"},{"key":"e_1_3_2_17_2","unstructured":"LLC Gurobi Optimization. 2020. Gurobi Optimizer Reference Manual. Retrieved May 2021 from http:\/\/www.gurobi.com."},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(00)00048-X"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0129053395000051"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1177\/1094342004041296"},{"key":"e_1_3_2_21_2","first-page":"558","volume-title":"Proceedings of the International Symposium on Algorithms and Computation","author":"JaJa Joseph","year":"2005","unstructured":"Joseph JaJa, Christian W. Mortensen, and Qingmin Shi. 2005. Space-efficient and fast algorithms for multidimensional dominance reporting and counting. In Proceedings of the International Symposium on Algorithms and Computation. Springer Berlin, 558\u2013568."},{"issue":"1","key":"e_1_3_2_22_2","first-page":"257","article-title":"Global hybrid simulations of the Earth\u2019s magnetosphere","volume":"359","author":"Karimabadi H.","year":"2006","unstructured":"H. Karimabadi, H. X. Vu, D. Krauss-Varban, and Y. Omelchenko. 2006. Global hybrid simulations of the Earth\u2019s magnetosphere. Numerical Modeling of Space Plasma Flows 359, 1 (Dec 2006), 257.","journal-title":"Numerical Modeling of Space Plasma Flows"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.5555\/646251.685987"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/SHPCC.1994.296689"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626407002843"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.5555\/645780.666193"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/0146-664X(82)90104-6"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1994.1126"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/71.491582"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2004.05.003"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0010-4655(02)00795-6"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.04.003"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2012.05.013"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/237578.237588"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144502409019"},{"key":"e_1_3_2_37_2","volume-title":"On symmetric rectilinear matrix partitioning","author":"Ya\u015far Abdurrahman","year":"2020","unstructured":"Abdurrahman Ya\u015far, Muhammed Fatih Bal\u0131n, Xiaojing An, Kaan Sancak, and \u00dcmit V. \u00c7ataly\u00fcrek. 2020. On symmetric rectilinear matrix partitioning. arXiv:2009.07735. Retrieved from http:\/\/arxiv.org\/abs\/2009.07735."},{"key":"e_1_3_2_38_2","doi-asserted-by":"crossref","first-page":"444","DOI":"10.1109\/TPDS.2021.3093240","article-title":"A block-based triangle counting algorithm on heterogeneous environments","volume":"33","author":"Ya\u015far Abdurrahman","year":"2021","unstructured":"Abdurrahman Ya\u015far, Sivasankaran Rajamanickam, Jonathan W. Berry, and \u00dcmit V. \u00c7ataly\u00fcrek. 2021. A block-based triangle counting algorithm on heterogeneous environments. IEEE Transactions on Parallel and Distributed Systems 33, 2 (2021), 444\u2013458.","journal-title":"IEEE Transactions on Parallel and Distributed Systems"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3523750","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3523750","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3523750","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:30:36Z","timestamp":1750188636000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3523750"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,31]]},"references-count":37,"alternative-id":["10.1145\/3523750"],"URL":"https:\/\/doi.org\/10.1145\/3523750","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,8,31]]}}}