{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T16:18:41Z","timestamp":1770913121309,"version":"3.50.1"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2026,2,28]]},"abstract":"<jats:p>\n                    In 1960, Osborne proposed a simple iterative algorithm for matrix balancing with outstanding numerical performance. Today, it is the default preconditioning procedure before eigenvalue computation and other linear algebra subroutines for square non-symmetric matrices in mainstream software packages such as Python, Julia, MATLAB, EISPACK, LAPACK, and more. Despite its widespread usage, Osborne\u2019s algorithm has long resisted theoretical guarantees for its runtime: the first polynomial-time guarantees were obtained only in the past decade, and recent near-linear runtimes remain confined to variants of Osborne\u2019s algorithm with important differences that make them simpler to analyze but empirically slower. In this paper, we address this longstanding gap between theory and practice by proving that Osborne\u2019s original algorithm\u2014the\n                    <jats:italic toggle=\"yes\">de facto<\/jats:italic>\n                    matrix balancing preconditioner in practice\u2014in fact has a near-linear runtime. This runtime guarantee (1) is optimal in the input size up to at most a single logarithm, (2) is the first runtime for Osborne\u2019s algorithm that does not dominate the runtime of downstream tasks like eigenvalue computation, and (3) improves upon the theoretical runtimes for all other variants of Osborne\u2019s algorithm.\n                  <\/jats:p>","DOI":"10.1145\/3779224","type":"journal-article","created":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T14:16:48Z","timestamp":1765030608000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Near-Linear Runtime for a Classical Matrix Preconditioning Algorithm"],"prefix":"10.1145","volume":"73","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-4379-6204","authenticated-orcid":false,"given":"Xufeng","family":"Cai","sequence":"first","affiliation":[{"name":"Department of Computer Sciences, University of Wisconsin-Madison","place":["Madison, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7367-0097","authenticated-orcid":false,"given":"Jason","family":"Altschuler","sequence":"additional","affiliation":[{"name":"Department of Statistics and Data Science, University of Pennsylvania","place":["Philadelphia, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3439-0310","authenticated-orcid":false,"given":"Jelena","family":"Diakonikolas","sequence":"additional","affiliation":[{"name":"Department of Computer Sciences, University of Wisconsin-Madison","place":["Madison, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,2,11]]},"reference":[{"key":"e_1_3_4_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.87"},{"key":"e_1_3_4_3_1","volume-title":"Proceedings of the Advances in Neural Information Processing Systems (NeurIPS)","author":"Altschuler Jason","year":"2017","unstructured":"Jason Altschuler, Jonathan Niles-Weed, and Philippe Rigollet. 2017. Near-linear time approximation algorithms for optimal transport via sinkhorn iteration. In Proceedings of the Advances in Neural Information Processing Systems (NeurIPS)."},{"key":"e_1_3_4_4_1","unstructured":"Jason M Altschuler. 2022. Flows scaling and entropy revisited: A unified perspective via optimizing joint distributions. SIAM Group on Optimization\u2019s Views and News (2022)."},{"key":"e_1_3_4_5_1","doi-asserted-by":"crossref","unstructured":"Jason M Altschuler and Pablo A Parrilo. 2022. Approximating min-mean-cycle for low-diameter graphs in near-optimal time and memory. SIAM Journal on Optimization 32 3 (2022) 1791\u20131816.","DOI":"10.1137\/21M1439390"},{"key":"e_1_3_4_6_1","doi-asserted-by":"crossref","unstructured":"Jason M Altschuler and Pablo A Parrilo. 2023. Near-linear convergence of the random osborne algorithm for matrix balancing. Mathematical Programming 198 1 (2023) 363\u2013397.","DOI":"10.1007\/s10107-022-01825-4"},{"key":"e_1_3_4_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/323215"},{"key":"e_1_3_4_8_1","doi-asserted-by":"crossref","unstructured":"Amir Beck and Luba Tetruashvili. 2013. On the convergence of block coordinate descent type methods. SIAM Journal on Optimization 23 4 (2013) 2037\u20132060.","DOI":"10.1137\/120887679"},{"key":"e_1_3_4_9_1","volume-title":"Parallel and Distributed Computation: Numerical Methods","author":"Bertsekas Dimitri","year":"2015","unstructured":"Dimitri Bertsekas and John Tsitsiklis. 2015. Parallel and Distributed Computation: Numerical Methods. Athena Scientific."},{"key":"e_1_3_4_10_1","volume-title":"Proceedings of the International Conference on Machine Learning (ICML)","author":"Cai Xufeng","year":"2023","unstructured":"Xufeng Cai, Chaobing Song, Stephen J Wright, and Jelena Diakonikolas. 2023. Cyclic block coordinate descent with variance reduction for composite nonconvex optimization. In Proceedings of the International Conference on Machine Learning (ICML)."},{"key":"e_1_3_4_11_1","volume-title":"Proceedings of the Advances in Neural Information Processing Systems (NeurIPS)","author":"Chakrabarti Darshan","year":"2023","unstructured":"Darshan Chakrabarti, Jelena Diakonikolas, and Christian Kroer. 2023. Block-coordinate methods and restarting for solving extensive-form games. In Proceedings of the Advances in Neural Information Processing Systems (NeurIPS)."},{"key":"e_1_3_4_12_1","volume-title":"Balancing Sparse Matrices for Computing Eigenvalues","author":"Chen T. Y.","year":"1998","unstructured":"T. Y. Chen. 1998. Balancing Sparse Matrices for Computing Eigenvalues. Master\u2019s thesis. University of California, Berkeley."},{"key":"e_1_3_4_13_1","doi-asserted-by":"crossref","unstructured":"Tzu-Yi Chen and James W Demmel. 2000. Balancing sparse matrices for computing eigenvalues. Linear Algebra and its Applications 309 1-3 (2000) 261\u2013287.","DOI":"10.1016\/S0024-3795(00)00014-8"},{"key":"e_1_3_4_14_1","volume-title":"Proceedings of the Symposium on Foundations of Computer Science (FOCS)","author":"Cohen Michael B","year":"2017","unstructured":"Michael B Cohen, Aleksander Madry, Dimitris Tsipras, and Adrian Vladu. 2017. Matrix scaling and balancing via box constrained newton\u2019s method and interior point methods. In Proceedings of the Symposium on Foundations of Computer Science (FOCS)."},{"key":"e_1_3_4_15_1","volume-title":"Proceedings of the Advances in Neural Information Processing Systems (NeurIPS)","author":"Cuturi Marco","year":"2013","unstructured":"Marco Cuturi. 2013. Sinkhorn distances: Lightspeed computation of optimal transport. In Proceedings of the Advances in Neural Information Processing Systems (NeurIPS)."},{"key":"e_1_3_4_16_1","doi-asserted-by":"crossref","unstructured":"B Curtis Eaves Alan J Hoffman Uriel G Rothblum and Hans Schneider. 1985. Line-sum-symmetric scalings of square nonnegative matrices. Mathematical Programming Essays in Honor of George B. Dantzig Part II (1985) 124\u2013141.","DOI":"10.1007\/BFb0121080"},{"key":"e_1_3_4_17_1","doi-asserted-by":"crossref","unstructured":"Edgar N Gilbert. 1959. Random graphs. The Annals of Mathematical Statistics 30 4 (1959) 1141\u20131144.","DOI":"10.1214\/aoms\/1177706098"},{"key":"e_1_3_4_18_1","doi-asserted-by":"crossref","unstructured":"Janez Grad. 1971. Matrix balancing. The Computer Journal 14 3 (1971) 280\u2013284.","DOI":"10.1093\/comjnl\/14.3.280"},{"key":"e_1_3_4_19_1","volume-title":"Proceedings of the Advances in Neural Information Processing Systems (NeurIPS)","author":"Gurbuzbalaban Mert","year":"2017","unstructured":"Mert Gurbuzbalaban, Asuman Ozdaglar, Pablo A Parrilo, and Nuri Vanli. 2017. When cyclic coordinate descent outperforms randomized coordinate descent. In Proceedings of the Advances in Neural Information Processing Systems (NeurIPS)."},{"key":"e_1_3_4_20_1","doi-asserted-by":"crossref","unstructured":"Darald J Hartfiel. 1971. Concerning diagonal similarity of irreducible matrices. Proceedings of the American Mathematical Society 30 3 (1971) 419\u2013425.","DOI":"10.1090\/S0002-9939-1971-0281731-5"},{"key":"e_1_3_4_21_1","doi-asserted-by":"crossref","unstructured":"Nicholas J Higham. 2005. The scaling and squaring method for the matrix exponential revisited. SIAM Journal on Matrix Analysis and Applications 26 4 (2005) 1179\u20131193.","DOI":"10.1137\/04061101X"},{"key":"e_1_3_4_22_1","unstructured":"Martin Idel. 2016. A review of matrix scaling and sinkhorn\u2019s normal form for matrices and positive maps. arXiv:1609.06349. Retrieved from https:\/\/arxiv.org\/abs\/1609.06349. (2016)."},{"key":"e_1_3_4_23_1","unstructured":"Julia. [n.d.]. LinearAlgebra.eigen: Compute eigenvalues and eigenvectors. Retrieved from https:\/\/docs.julialang.org\/en\/v1\/stdlib\/LinearAlgebra\/#LinearAlgebra.eigen"},{"key":"e_1_3_4_24_1","doi-asserted-by":"crossref","unstructured":"Bahman Kalantari Leonid Khachiyan and Ali Shokoufandeh. 1997. On the complexity of matrix balancing. SIAM Journal on Matrix Analysis and Applications 18 2 (1997) 450\u2013463.","DOI":"10.1137\/S0895479895289765"},{"key":"e_1_3_4_25_1","doi-asserted-by":"crossref","unstructured":"Ching-pei Lee and Stephen J Wright. 2020. Inexact variable metric stochastic block-coordinate descent for regularized optimization. Journal of Optimization Theory and Applications 185 1 (2020) 151\u2013187.","DOI":"10.1007\/s10957-020-01639-4"},{"key":"e_1_3_4_26_1","volume-title":"Proceedings of the International Conference on Machine Learning (ICML)","author":"Lin Cheuk Yin","year":"2023","unstructured":"Cheuk Yin Lin, Chaobing Song, and Jelena Diakonikolas. 2023. Accelerated cyclic coordinate dual averaging with extrapolation for composite convex optimization. In Proceedings of the International Conference on Machine Learning (ICML)."},{"key":"e_1_3_4_27_1","unstructured":"MathWorks. [n.d.]. eig: eigenvalues and eigenvectors. Retrieved from https:\/\/www.mathworks.com\/help\/matlab\/ref\/eig.html"},{"key":"e_1_3_4_28_1","unstructured":"NumPy. [n.d.]. numpy.linalg.eig: Compute the eigenvalues and right eigenvectors of a square array. Retrieved from https:\/\/numpy.org\/doc\/stable\/reference\/generated\/numpy.linalg.eig.html"},{"key":"e_1_3_4_29_1","doi-asserted-by":"crossref","unstructured":"EE Osborne. 1960. On pre-conditioning of matrices. Journal of the ACM 7 4 (1960) 338\u2013345.","DOI":"10.1145\/321043.321048"},{"key":"e_1_3_4_30_1","volume-title":"Proceedings of the Symposium on Discrete Algorithms (SODA)","author":"Ostrovsky Rafail","year":"2017","unstructured":"Rafail Ostrovsky, Yuval Rabani, and Arman Yousefi. 2017. Matrix balancing in \\(L_p\\) norms: Bounding the convergence rate of osborne\u2019s iteration. In Proceedings of the Symposium on Discrete Algorithms (SODA)."},{"key":"e_1_3_4_31_1","volume-title":"Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP)","author":"Ostrovsky Rafail","year":"2018","unstructured":"Rafail Ostrovsky, Yuval Rabani, and Arman Yousefi. 2018. Strictly balancing matrices in polynomial time using osborne\u2019s iteration. In Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP)."},{"key":"e_1_3_4_32_1","doi-asserted-by":"crossref","unstructured":"Beresford N Parlett and Christian Reinsch. 1969. Balancing a matrix for calculation of eigenvalues and eigenvectors. Numerische Mathematik 13 (1969) 293\u2013304.","DOI":"10.1007\/BF02165404"},{"key":"e_1_3_4_33_1","doi-asserted-by":"crossref","unstructured":"Gabriel Peyr\u00e9 and Marco Cuturi. 2019. Computational optimal transport: With applications to data science. Foundations and Trends\u00ae in Machine Learning 11 5-6 (2019) 355\u2013607.","DOI":"10.1561\/2200000073"},{"key":"e_1_3_4_34_1","volume-title":"Numerical Recipes 3rd Edition: The art of Scientific Computing","author":"Press William H","year":"2007","unstructured":"William H Press. 2007. Numerical Recipes 3rd Edition: The art of Scientific Computing. Cambridge University Press."},{"key":"e_1_3_4_35_1","doi-asserted-by":"crossref","unstructured":"Hans Schneider and Michael H Schneider. 1991. Max-balancing weighted directed graphs and matrix scaling. Mathematics of Operations Research 16 1 (1991) 208\u2013222.","DOI":"10.1287\/moor.16.1.208"},{"key":"e_1_3_4_36_1","doi-asserted-by":"crossref","unstructured":"Michael H Schneider and Stavros A Zenios. 1990. A comparative study of algorithms for matrix balancing. Operations Research 38 3 (1990) 439\u2013455.","DOI":"10.1287\/opre.38.3.439"},{"key":"e_1_3_4_37_1","doi-asserted-by":"crossref","unstructured":"Leonard J Schulman and Alistair Sinclair. 2017. Analysis of a classical matrix preconditioning algorithm. Journal of the ACM 64 2 (2017) 1\u201323.","DOI":"10.1145\/2988227"},{"key":"e_1_3_4_38_1","doi-asserted-by":"crossref","unstructured":"Richard Sinkhorn. 1967. Diagonal equivalence to matrices with prescribed row and column sums. The American Mathematical Monthly 74 4 (1967) 402\u2013405.","DOI":"10.2307\/2314570"},{"key":"e_1_3_4_39_1","volume-title":"Matrix Eigensystem Routines-EISPACK Guide","author":"Smith Brian T","year":"2013","unstructured":"Brian T Smith, James M. Boyle, BS Garbow, Y Ikebe, VC Klema, and CB Moler. 2013. Matrix Eigensystem Routines-EISPACK Guide. Vol. 6. Springer."},{"key":"e_1_3_4_40_1","doi-asserted-by":"crossref","unstructured":"Chaobing Song and Jelena Diakonikolas. 2023. Cyclic coordinate dual averaging with extrapolation. SIAM Journal on Optimization 33 4 (2023) 2935\u20132961.","DOI":"10.1137\/22M1470104"},{"key":"e_1_3_4_41_1","doi-asserted-by":"crossref","unstructured":"Ruoyu Sun and Yinyu Ye. 2021. Worst-case complexity of cyclic coordinate descent: \\(O (n^2)\\) gap with randomized version. Mathematical Programming 185 1 (2021) 487\u2013520.","DOI":"10.1007\/s10107-019-01437-5"},{"key":"e_1_3_4_42_1","doi-asserted-by":"crossref","unstructured":"Robert Tarjan. 1972. Depth-first search and linear graph algorithms. SIAM Journal on Computing 1 2 (1972) 146\u2013160.","DOI":"10.1137\/0201010"},{"key":"e_1_3_4_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/775152.775202"},{"key":"e_1_3_4_44_1","doi-asserted-by":"crossref","unstructured":"Robert C Ward. 1977. Numerical computation of the matrix exponential with accuracy estimate. SIAM Journal on Numerical Analysis 14 4 (1977) 600\u2013610.","DOI":"10.1137\/0714039"},{"key":"e_1_3_4_45_1","doi-asserted-by":"crossref","unstructured":"Stephen Wright and Ching-pei Lee. 2020. Analyzing random permutations for cyclic coordinate descent. Mathematics of Computation 89 325 (2020) 2217\u20132248.","DOI":"10.1090\/mcom\/3530"},{"key":"e_1_3_4_46_1","doi-asserted-by":"crossref","unstructured":"Stephen J Wright. 2015. Coordinate descent algorithms. Mathematical Programming 151 1 (2015) 3\u201334.","DOI":"10.1007\/s10107-015-0892-3"},{"key":"e_1_3_4_47_1","doi-asserted-by":"crossref","unstructured":"Neal E Young Robert E Tarjan and James B Orlin. 1991. Faster parametric shortest path and minimum-balance algorithms. Networks 21 2 (1991) 205\u2013221.","DOI":"10.1002\/net.3230210206"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3779224","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T15:28:43Z","timestamp":1770910123000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3779224"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,11]]},"references-count":46,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,2,28]]}},"alternative-id":["10.1145\/3779224"],"URL":"https:\/\/doi.org\/10.1145\/3779224","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,11]]},"assertion":[{"value":"2025-03-25","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-11-10","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-02-11","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}