{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:24:50Z","timestamp":1787336690144,"version":"build-2736575974"},"reference-count":51,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"name":"BAGEP Award of the Science Academy"},{"name":"National Center for High Performance Computing of Turkey","award":["1008172020"],"award-info":[{"award-number":["1008172020"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2023,4,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>The block Cimmino is a parallel hybrid row-block projection iterative method successfully used for solving general sparse linear systems. However, the convergence of the method degrades when angles between subspaces spanned by the row-blocks are far from being orthogonal. The density of columns as well as the numerical values of their nonzeros are more likely to contribute to the nonorthogonality between row-blocks. We propose a novel scheme to handle such \u201cdense\u201d columns. The proposed scheme forms a reduced system by separating these columns and the respective rows from the original coefficient matrix and handling them via the Schur complement. Then the angles between subspaces spanned by the row-blocks of the reduced system are expected to be closer to orthogonal, and the reduced system is solved efficiently by the block conjugate gradient (CG) accelerated block Cimmino in fewer iterations. We also propose a novel metric for selecting \u201cdense\u201d columns considering the numerical values. The proposed metric establishes an upper bound on the sum of inner products between row-blocks. Then we propose an efficient algorithm for computing the proposed metric for the columns. Extensive numerical experiments for a wide range of linear systems confirm the effectiveness of the proposed scheme by achieving fewer iterations and faster parallel solution time compared to the classical CG accelerated block Cimmino algorithm.<\/jats:p>","DOI":"10.1137\/21m1453475","type":"journal-article","created":{"date-parts":[[2023,4,7]],"date-time":"2023-04-07T04:15:22Z","timestamp":1680840922000},"page":"C49-C72","source":"Crossref","is-referenced-by-count":3,"title":["Enhancing Block Cimmino for Sparse Linear Systems with Dense Columns via Schur Complement"],"prefix":"10.1137","volume":"45","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6662-2502","authenticated-orcid":true,"given":"F. Sukru","family":"Torun","sequence":"first","affiliation":[{"name":"Department of Computer Engineering, Ankara Yildirim Beyazit University, Ankara 06020, Turkey."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Murat","family":"Manguoglu","sequence":"additional","affiliation":[{"name":"Department of Computer Engineering, Middle East Technical University, Ankara 06800, Turkey."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Cevdet","family":"Aykanat","sequence":"additional","affiliation":[{"name":"Department of Computer Engineering, Bilkent University, Ankara 06800, Turkey."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2023,4,7]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1099-1506(200003)7:2<51::AID-NLA187>3.0.CO;2-O"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479899358194"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1145\/232826.232937"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1007\/BF02242280"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1007\/BF01389335"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1137\/0913003"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1137\/0916086"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1137\/070698725"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1986-6_8"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1006\/jcph.2002.7176"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611971484"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1007\/BF01934122"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1137\/0913010"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1080\/10556789608805643"},{"key":"ref15","volume-title":"Calcolo approssimato per le soluzioni dei sistemi di equazioni lineari","author":"Cimmino G.","year":"1938"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1145\/2049662.2049663"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1137\/0614001"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1007\/s101070100263"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1007\/s10665-014-9699-0"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1137\/140961444"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479899358443"},{"key":"ref22","doi-asserted-by":"crossref","unstructured":"R. D. Falgout  and \nU. M. Yang , hypre: A library of high performance preconditioners, in International Conference on Computational Science, Springer, New York, 2002, pp. 632\u2013641.","DOI":"10.1007\/3-540-47789-6_66"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(80)90159-7"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1016\/0022-5193(72)90180-4"},{"key":"ref25","doi-asserted-by":"crossref","unstructured":"P. E. Gill , \nW. Murray , \nD. B. Ponceleon , and \nM. A. Saunders , Solving Reduced KKT Systems in Barrier Methods for Linear and Quadratic Programming, Technical report SOL 91-7, Stanford University, Stanford, CA, 1991.","DOI":"10.21236\/ADA239191"},{"key":"ref26","first-page":"276","volume":"3","author":"Giraud L.","year":"2010","journal-title":"Numer. Math."},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-003-0377-7"},{"key":"ref28","doi-asserted-by":"crossref","unstructured":"G. H. Golub  and \nM. A. Saunders , Linear Least Squares and Quadratic Programming, Technical report, Stanford University, Stanford, CA, 1969.","DOI":"10.21236\/AD0700923"},{"key":"ref29","volume-title":"Matrix Computations","author":"Golub G. H.","year":"1983"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1080\/02331939208843796"},{"key":"ref31","unstructured":"HSL, A Collection of Fortran Codes for Large Scale Scientific Computation, http:\/\/www.hsl.rl.ac.uk, 2007."},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1007\/s10543-016-0631-z"},{"key":"ref33","first-page":"355","volume":"35","author":"Kaczmarz S.","year":"1937","journal-title":"Bull. Int. Acad. Pol. Sci. Lett."},{"key":"ref34","unstructured":"G. Karypis  and \nV. Kumar , Metis: Unstructured Graph Partitioning and Sparse Matrix Ordering System, Version 5.1, http:\/\/www.cs.umn.edu\/\u223cmetis, 2013."},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-006-9008-6"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(80)90247-5"},{"key":"ref37","unstructured":"D. Ruiz , Solution of large sparse unsymmetric linear systems with a block iterative method in a multiprocessor environment, CERFACS TH\/PA\/9, 6, 1992."},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1137\/0907058"},{"key":"ref39","first-page":"92","volume-title":"Linear and Nonlinear Conjugate Gradient-Related Methods","author":"Saunders M. A.","year":"1996"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1137\/16M1108339"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1007\/s11075-018-0478-2"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1137\/18M1181353"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(05)80146-2"},{"key":"ref44","unstructured":"C. Sun , Dealing with dense rows in the solution of sparse linear least squares problems, Technical report, Advanced Computing Research Institute, Cornell Theory Center, Cornell University, 1995."},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(97)00064-1"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1137\/18M1166407"},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1137\/0913035"},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(91)90269-3"},{"key":"ref49","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-9274(01)00115-5"},{"key":"ref50","unstructured":"M. Zenadi , M\u00e9thodes hybrides pour la r\u00e9solution de grands syst\u00e8mes lin\u00e9aires creux sur calculateurs parall\u00e8les, Ph.D. thesis, \u00c9cole Doctorale Math\u00e9matiques, Informatique et T\u00e9l\u00e9communications (Toulouse), 142547247, 2013."},{"key":"ref51","unstructured":"M. Zenadi , \nD. Ruiz , and \nR. Guivarch , The Augmented Block Cimmino Distributed Solver, ABCD Solver v1.0, http:\/\/abcd.enseeiht.fr, 2021."}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/21M1453475","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:26:36Z","timestamp":1787333196000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/21M1453475"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,7]]},"references-count":51,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,4,30]]}},"alternative-id":["10.1137\/21M1453475"],"URL":"https:\/\/doi.org\/10.1137\/21m1453475","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,4,7]]}}}