{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:31:46Z","timestamp":1787329906909,"version":"build-2736575974"},"reference-count":41,"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":[[2023,2,28]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>We present an algebraic framework for operator splitting preconditioners for general sparse matrices. The framework leads to four different approaches: two with alternating splittings and two with a multiplicative ansatz. The ansatz generalizes ADI and ILU methods to multiple factors and to a more general factor form. The factors may be computed directly from the matrix coefficients or adaptively by incomplete sparse inversions. The special case of tridiagonal splittings is examined in more detail. We decompose the adjacency graph of the sparse matrix into multiple (almost) disjoint linear forests, and each linear forest (a union of disjoint paths) leads to a tridiagonal splitting. We obtain specialized variants of the four general approaches. Parallel implementations for all steps are provided on a GPU. We demonstrate the effectiveness and efficiency of these preconditioners combined with GMRES on various matrices.<\/jats:p>","DOI":"10.1137\/21m1430492","type":"journal-article","created":{"date-parts":[[2023,1,24]],"date-time":"2023-01-24T11:28:05Z","timestamp":1674559685000},"page":"A25-A48","source":"Crossref","is-referenced-by-count":0,"title":["Preconditioning Sparse Matrices with Alternating and Multiplicative Operator Splittings"],"prefix":"10.1137","volume":"45","author":[{"given":"Christoph","family":"Klein","sequence":"first","affiliation":[{"name":"Institute of Computer Engineering (ZITI), Heidelberg University, Heidelberg 69120, Germany."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Robert","family":"Strzodka","sequence":"additional","affiliation":[{"name":"Institute of Computer Engineering (ZITI), Heidelberg University, Heidelberg 69120, Germany."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2023,1,27]]},"reference":[{"key":"ref1","doi-asserted-by":"crossref","unstructured":"P. Alfaro , \nP. Igounet , and \nP. Ezzatti , A study on the implementation of tridiagonal systems solvers using a GPU, in Proceedings of the 2011 30th International Conference of the Chilean Computer Science Society, IEEE Press, Piscataway, NJ, 2011, pp. 219\u2013227, https:\/\/doi.org\/10.1109\/SCCC.2011.29.","DOI":"10.1109\/SCCC.2011.29"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1007\/PL00007233"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1016\/j.camwa.2020.06.009"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2017.10.003"},{"key":"ref5","doi-asserted-by":"crossref","unstructured":"H. Anzt , \nW. Sawyer , \nS. Tomov , \nP. Luszczek , \nI. Yamazaki , and \nJ. Dongarra , Optimizing Krylov subspace solvers on graphics processing units, in Proceedings of the IEEE 28th International Parallel and Distributed Processing Symposium Workshops (IPDPSW 2014), Phoenix, AZ, IEEE Press, Piscataway, NJ, 2014, pp. 941\u2013949, https:\/\/doi.org\/10.1109\/IPDPSW.2014.107.","DOI":"10.1109\/IPDPSW.2014.107"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1137\/100798806"},{"key":"ref7","unstructured":"L.W. Chang , Scalable Parallel Tridiagonal Algorithms with Diagonal Pivoting and Their Optimization for Many-Core Architectures, Ph.D. thesis, 2014."},{"key":"ref8","first-page":"1","author":"Chang L.-W.","year":"2012","journal-title":"International Conference on for High Performance Computing, Networking, Storage and Analysis"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1137\/140968896"},{"key":"ref10","first-page":"58","volume-title":"Gtc","author":"Cohen J.","year":"2012"},{"key":"ref11","doi-asserted-by":"crossref","unstructured":"A. Davidson , \nY. Zhang , and \nJ. D. Owens , An auto-tuned method for solving large tridiagonal systems on the GPU, in Proceedings of the 25th IEEE International Parallel and Distributed Processing Symposium (IPDPS), IEEE Press, Piscataway, NJ, 2011, pp. 956\u2013965, https:\/\/doi.org\/10.1109\/IPDPS.2011.92.","DOI":"10.1109\/IPDPS.2011.92"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1145\/2049662.2049663"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53622-3"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386295"},{"key":"ref15","first-page":"279","volume":"17","author":"Douglas J.","year":"1963","journal-title":"Math. Comput."},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-12-358502-8.50009-8"},{"key":"ref17","doi-asserted-by":"crossref","unstructured":"R. D. Falgout  and \nU. M. Yang , hypre: A library of high performance preconditioners, in Proceedings of the International Conference on Computer Science, Lecture Notes in Comput. Sci. 2331, 2002, \nP. M. A. Sloot  et al., eds. Springer, Berlin, pp. 632\u2013641, https:\/\/doi.org\/10.1007\/3-540-47789-6_66.","DOI":"10.1007\/3-540-47789-6_66"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-41589-5"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2010.61"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1080\/17445760601122076"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1016\/j.apnum.2015.08.012"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1111\/j.1749-6632.1970.tb56470.x"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-09017-6"},{"key":"ref24","first-page":"1","author":"Kass M.","year":"2006","journal-title":"Computing"},{"key":"ref25","doi-asserted-by":"crossref","unstructured":"H. S. Kim , \nS. Wu , \nL. W. Chang , and \nW. M. W. Hwu , A scalable tridiagonal solver for GPUs, in Proceedings of the 2011 International Conference on Parallel Processing, IEEE Press, Piscataway, NJ, 2011, pp. 444\u2013453, https:\/\/doi.org\/10.1109\/ICPP.2011.41.","DOI":"10.1109\/ICPP.2011.41"},{"key":"ref26","doi-asserted-by":"crossref","unstructured":"C. Klein  and \nR. Strzodka , Tridiagonal GPU solver with scaled partial pivoting at maximum bandwidth, in Proceedings of ICPP 2021: 50th International Conference on Parallel Processing 54, ACM, New York, 2021, https:\/\/doi.org\/10.1145\/3472456.3472484.","DOI":"10.1145\/3472456.3472484"},{"key":"ref27","doi-asserted-by":"crossref","unstructured":"C. Klein  and \nR. Strzodka , Highly parallel linear forest extraction from a weighted graph on GPUs, in ACM International Conference Proceeding Series, ACM, Bordeaux, France, 2022, pp. 1\u201311, https:\/\/doi.org\/10.1145\/3545008.3545035.","DOI":"10.1145\/3545008.3545035"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1109\/LAWP.2008.2002316"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.4236\/am.2013.47146"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1006\/jcph.1998.6036"},{"key":"ref31","unstructured":"M. Naumov , \nL. Chien , \nP. Vandermersch , and \nU. Kapasi , Cusparse library, in Proceedings of the GPU Technology Conference, 2010."},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1137\/0103003"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386310"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1016\/j.cam.2011.11.016"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718003"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1109\/TAP.2007.913089"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-0427(00)00523-9"},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-5122-8"},{"key":"ref40","first-page":"155","volume-title":"SIAM Rev.","volume":"12","author":"Wilcox C. H.","year":"1996"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1016\/j.cam.2015.03.005"},{"key":"ref42","doi-asserted-by":"crossref","unstructured":"Z. Zhu , \nR. Shi , \nC. K. Cheng , and \nE. S. Kuh , An unconditional stable general operator splitting method for transistor level transient analysis, in ASP-DAC\u201806: Proceedings of the 2006 Asia and South Pacific Design Automation Conference, IEEE Press, Piscataway, NJ, 2006, pp. 428\u2013433, https:\/\/doi.org\/10.1145\/1118299.1118403.","DOI":"10.1145\/1118299.1118403"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/21M1430492","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:38:43Z","timestamp":1787326723000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/21M1430492"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,27]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,2,28]]}},"alternative-id":["10.1137\/21M1430492"],"URL":"https:\/\/doi.org\/10.1137\/21m1430492","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,1,27]]}}}