{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T07:12:12Z","timestamp":1787382732495,"version":"3.56.0"},"reference-count":38,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"publisher","award":["DE-AC02-06CH11347"],"award-info":[{"award-number":["DE-AC02-06CH11347"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100001395","name":"Wisconsin Alumni Research Foundation","doi-asserted-by":"publisher","award":["AAD5914"],"award-info":[{"award-number":["AAD5914"]}],"id":[{"id":"10.13039\/100001395","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Matrix Anal. Appl."],"published-print":{"date-parts":[[2023,9,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>Randomized linear solvers randomly compress and solve a linear system with compelling theoretical convergence rates and computational complexities. However, such solvers suffer a substantial disconnect between their theoretical rates and actual efficiency in practice. Fortunately, these solvers are quite flexible and can be adapted to specific problems and computing environments to ensure high efficiency in practice, even at the cost of lower effectiveness (i.e., having a slower theoretical rate of convergence). While highly efficient adapted solvers can be readily designed by application experts, will such solvers still converge and at what rate? To answer this, we distill three general criteria for randomized adaptive solvers, which, as we show, will guarantee a worst-case exponential rate of convergence of the solver applied to consistent and inconsistent linear systems irrespective of whether such systems are overdetermined, underdetermined, or rank deficient. As a result, we enable application experts to design randomized adaptive solvers that achieve efficiency and can be verified for effectiveness using our theory. We demonstrate our theory on 26 solvers, nine of which are novel or novel block extensions of existing methods to the best of our knowledge.<\/jats:p>","DOI":"10.1137\/22m1488715","type":"journal-article","created":{"date-parts":[[2023,9,6]],"date-time":"2023-09-06T04:18:46Z","timestamp":1693973926000},"page":"1349-1369","source":"Crossref","is-referenced-by-count":3,"title":["Randomized Block Adaptive Linear System Solvers"],"prefix":"10.1137","volume":"44","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4130-0897","authenticated-orcid":true,"given":"Vivak","family":"Patel","sequence":"first","affiliation":[{"name":"Department of Statistics, University of Wisconsin\u2013Madison, Madison, WI 53706 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mohammad","family":"Jahangoshahi","sequence":"additional","affiliation":[{"name":"Susquehanna International Group, Bala Cynwyd, PA 19004 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6511-9051","authenticated-orcid":true,"given":"D. Adrian","family":"Maldonado","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science, Argonne National Laboratories, Lemont, IL 60439 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2023,9,6]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1954-037-2"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1007\/s00211-012-0512-6"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1137\/17M1137747"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1137\/040608088"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1109\/LSP.2015.2412253"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1145\/1070838.1070856"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-39-00552-1"},{"key":"ref8","doi-asserted-by":"crossref","DOI":"10.56021\/9781421407944","volume-title":"Matrix Computations","volume":"3","author":"Golub G. H.","year":"2012"},{"key":"ref9","unstructured":"R. Gower , \nD. Molitor , \nJ. Moorman , and \nD. Needell , Adaptive Sketch-and-Project Methods for Solving Linear Systems, preprint, https:\/\/arxiv.org\/abs\/1909.03604, 2019."},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1137\/19M1285846"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1137\/15M1025487"},{"key":"ref12","unstructured":"J. Haddock  and \nA. Ma , Greed Works: An Improved Analysis of Sampling Kaczmarz-Motkzin, preprint, https:\/\/arxiv.org\/abs\/1912.03544, 2019."},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1080\/00207179308934446"},{"key":"ref14","first-page":"355","volume":"35","author":"Kaczmarz S.","year":"1937","journal-title":"Bull. Int. Acad. Pol. Sci. Let."},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492920000021"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1137\/0706011"},{"key":"ref17","volume-title":"Markov Chains and Stochastic Stability","author":"Meyn S. P.","year":"2012"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1954-038-x"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1137\/19M1251643"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1137\/130950288"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2012.12.022"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2015.06.027"},{"key":"ref23","unstructured":"J. Nutini , \nB. Sepehry , \nI. Laradji , \nM. Schmidt , \nH. Koepke , and \nA. Virani , Convergence Rates for Greedy Kaczmarz Algorithms, and Faster Randomized Kaczmarz Rules Using the Orthogonality Graph, preprint, https:\/\/arxiv.org\/abs\/1612.07838, 2016."},{"key":"ref24","unstructured":"V. Patel , \nM. Jahangoshahi , and \nD. A. Maldonado , Convergence of Adaptive, Randomized, Iterative Linear Solvers, preprint, https:\/\/arxiv.org\/abs\/2104.04816, 2021."},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1137\/19M1259481"},{"key":"ref26","first-page":"1","volume":"17","author":"Pilanci M.","year":"2016","journal-title":"J. Mach. Learn. Res."},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.2307\/1988879"},{"key":"ref28","unstructured":"N. Pritchard  and \nV. Patel , Residual Tracking and Stopping for Iterative Random Sketching, preprint, https:\/\/arxiv.org\/abs\/2201.05741, 2022."},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1007\/s11075-020-00895-9"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1137\/18M1179249"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718003"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1090\/mcom\/3644"},{"key":"ref33","unstructured":"S. Steinerberger , Approximate Solutions of Linear Systems at a Universal Rate, preprint, https:\/\/arxiv.org\/abs\/2207.03388, 2022."},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1007\/s00041-008-9030-4"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1137\/0111043"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1561\/0400000060"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1090\/mcom\/3530"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1137\/120889897"}],"container-title":["SIAM Journal on Matrix Analysis and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/22M1488715","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:23:49Z","timestamp":1787325829000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/22M1488715"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,6]]},"references-count":38,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,9,30]]}},"alternative-id":["10.1137\/22M1488715"],"URL":"https:\/\/doi.org\/10.1137\/22m1488715","relation":{},"ISSN":["0895-4798","1095-7162"],"issn-type":[{"value":"0895-4798","type":"print"},{"value":"1095-7162","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,9,6]]}}}