Thanks to its great potential in reducing both computational cost and memory requirements, combining sketching and Krylov subspace techniques has attracted a lot of attention in the recent literature on projection methods for linear systems, matrix function approximations, and eigenvalue problems. Applying this appealing strategy in the context of linear matrix equations turns out to be far more involved than a straightforward generalization. These difficulties include analyzing well-posedness of the projected problem and deriving possible error estimates depending on the sketching properties. Further computational complications include the lack of a natural residual norm estimate and of an explicit basis for the generated subspace.<\/p>\n
In this paper we propose a new sketched-and-truncated polynomial Krylov subspace method for Sylvester equations that aims to address all these issues. The potential of our novel approach, in terms of both computational time and storage demand, is illustrated with numerical experiments. Comparisons with a state-of-the-art projection scheme based on rational Krylov subspaces are also included.<\/p>","DOI":"10.1090\/mcom\/4002","type":"journal-article","created":{"date-parts":[[2024,7,9]],"date-time":"2024-07-09T13:04:56Z","timestamp":1720530296000},"page":"1761-1792","source":"Crossref","is-referenced-by-count":2,"title":["Sketched and truncated polynomial Krylov subspace methods: Matrix Sylvester equations"],"prefix":"10.1090","volume":"94","author":[{"given":"Davide","family":"Palitta","sequence":"first","affiliation":[]},{"given":"Marcel","family":"Schweitzer","sequence":"additional","affiliation":[]},{"given":"Valeria","family":"Simoncini","sequence":"additional","affiliation":[]}],"member":"14","published-online":{"date-parts":[[2024,7,25]]},"reference":[{"key":"1","series-title":"Advances in Design and Control","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718713","volume-title":"Approximation of large-scale dynamical systems","volume":"6","author":"Antoulas, Athanasios C.","year":"2005","ISBN":"https:\/\/id.crossref.org\/isbn\/0898715296"},{"key":"2","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1090\/qam\/42792","article-title":"The principle of minimized iteration in the solution of the matrix eigenvalue problem","volume":"9","author":"Arnoldi, W. E.","year":"1951","journal-title":"Quart. Appl. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0033-569X","issn-type":"print"},{"issue":"2","key":"3","doi-asserted-by":"publisher","first-page":"656","DOI":"10.1137\/140993867","article-title":"Fast singular value decay for Lyapunov solutions with nonnormal coefficients","volume":"36","author":"Baker, Jonathan","year":"2015","journal-title":"SIAM J. Matrix Anal. Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0895-4798","issn-type":"print"},{"key":"4","unstructured":"O. Balabanov and L. Grigori, Randomized block Gram\u2013Schmidt process for solution of linear systems and eigenvalue problems, arXiv preprint arXiv:2111.14641 (2021)."},{"key":"5","doi-asserted-by":"crossref","unstructured":"O. Balabanov and L. Grigori, Randomized Gram\u2013Schmidt process with application to GMRES, SIAM J. Sci. Comput. 44 (2022), no. 3, A1450\u2013A1474.","DOI":"10.1137\/20M138870X"},{"issue":"5-6","key":"6","doi-asserted-by":"publisher","first-page":"2969","DOI":"10.1007\/s10444-019-09725-6","article-title":"Randomized linear algebra for model reduction. Part I: Galerkin methods and error estimation","volume":"45","author":"Balabanov, Oleg","year":"2019","journal-title":"Adv. Comput. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/1019-7168","issn-type":"print"},{"key":"7","doi-asserted-by":"crossref","unstructured":"R. H. Bartels and G. W. Stewart, Solution of the matrix equation \ud835\udc4e\ud835\udc65+\ud835\udc65\ud835\udc4f=\ud835\udc50, Commun. ACM 15 (1972), no. 9, 820\u2013826.","DOI":"10.1145\/361573.361582"},{"issue":"9","key":"8","doi-asserted-by":"publisher","first-page":"837","DOI":"10.1002\/nla.605","article-title":"Low rank solution of data-sparse Sylvester equations","volume":"15","author":"Baur, U.","year":"2008","journal-title":"Numer. Linear Algebra Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/1070-5325","issn-type":"print"},{"issue":"11","key":"9","doi-asserted-by":"publisher","first-page":"855","DOI":"10.1016\/j.crma.2005.04.027","article-title":"Image num\u00e9rique, GMRES et polyn\u00f4mes de Faber","volume":"340","author":"Beckermann, Bernhard","year":"2005","journal-title":"C. R. Math. Acad. Sci. Paris","ISSN":"https:\/\/id.crossref.org\/issn\/1631-073X","issn-type":"print"},{"issue":"4","key":"10","doi-asserted-by":"publisher","first-page":"1035","DOI":"10.1016\/j.cam.2009.08.108","article-title":"On the ADI method for Sylvester equations","volume":"233","author":"Benner, Peter","year":"2009","journal-title":"J. Comput. Appl. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0377-0427","issn-type":"print"},{"issue":"1","key":"11","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1002\/gamm.201310003","article-title":"Numerical solution of large and sparse continuous time algebraic matrix Riccati and Lyapunov equations: a state of the art survey","volume":"36","author":"Benner, Peter","year":"2013","journal-title":"GAMM-Mitt.","ISSN":"https:\/\/id.crossref.org\/issn\/0936-7195","issn-type":"print"},{"key":"12","series-title":"Fundamentals of Algorithms","isbn-type":"print","volume-title":"Numerical solution of algebraic Riccati equations","volume":"9","author":"Bini, Dario A.","year":"2012","ISBN":"https:\/\/id.crossref.org\/isbn\/9781611972085"},{"key":"13","doi-asserted-by":"crossref","unstructured":"L. Burke and S. G\u00fcttel, Krylov subspace recycling with randomized sketching for matrix functions, arXiv preprint arXiv:2308.02290 (2023).","DOI":"10.1137\/23M1595904"},{"issue":"4","key":"14","doi-asserted-by":"publisher","first-page":"1742","DOI":"10.1137\/20M1310497","article-title":"Structured random sketching for PDE inverse problems","volume":"41","author":"Chen, Ke","year":"2020","journal-title":"SIAM J. Matrix Anal. Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0895-4798","issn-type":"print"},{"issue":"1","key":"15","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1137\/22M1543458","article-title":"Speeding up Krylov subspace methods for computing \ud835\udc53(\ud835\udc34)\ud835\udc4f via randomization","volume":"45","author":"Cortinovis, Alice","year":"2024","journal-title":"SIAM J. Matrix Anal. Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0895-4798","issn-type":"print"},{"key":"16","isbn-type":"print","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1007\/11830924_30","article-title":"Subspace sampling and relative-error matrix approximation: column-based methods","author":"Drineas, Petros","year":"2006","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540380443"},{"issue":"8","key":"17","doi-asserted-by":"publisher","first-page":"546","DOI":"10.1016\/j.sysconle.2011.04.013","article-title":"Adaptive rational Krylov subspaces for large-scale dynamical systems","volume":"60","author":"Druskin, V.","year":"2011","journal-title":"Systems Control Lett.","ISSN":"https:\/\/id.crossref.org\/issn\/0167-6911","issn-type":"print"},{"issue":"6","key":"18","doi-asserted-by":"publisher","first-page":"2481","DOI":"10.1137\/050633846","article-title":"A restarted Krylov subspace method for the evaluation of matrix functions","volume":"44","author":"Eiermann, Michael","year":"2006","journal-title":"SIAM J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0036-1429","issn-type":"print"},{"issue":"2","key":"19","doi-asserted-by":"publisher","first-page":"804","DOI":"10.1137\/19M1255847","article-title":"Block Krylov subspace methods for functions of matrices II: Modified block FOM","volume":"41","author":"Frommer, Andreas","year":"2020","journal-title":"SIAM J. Matrix Anal. Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0895-4798","issn-type":"print"},{"key":"20","isbn-type":"print","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/978-3-540-78841-6_13","article-title":"Matrix functions","author":"Frommer, Andreas","year":"2008","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540788409"},{"issue":"4","key":"21","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1002\/nla.366","article-title":"Existence of a low rank or \u210b-matrix approximant to the solution of a Sylvester equation","volume":"11","author":"Grasedyck, L.","year":"2004","journal-title":"Numer. Linear Algebra Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/1070-5325","issn-type":"print"},{"issue":"3","key":"22","doi-asserted-by":"publisher","first-page":"870","DOI":"10.1137\/040618102","article-title":"A multigrid method to solve large scale Sylvester equations","volume":"29","author":"Grasedyck, Lars","year":"2007","journal-title":"SIAM J. Matrix Anal. Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0895-4798","issn-type":"print"},{"key":"23","unstructured":"L. Grigori and E. Timsit, Randomized Householder QR, Tech. report, 2023."},{"issue":"3","key":"24","doi-asserted-by":"publisher","first-page":"1073","DOI":"10.1137\/22M1518062","article-title":"Randomized sketching for Krylov approximations of large-scale matrix functions","volume":"44","author":"G\u00fcttel, Stefan","year":"2023","journal-title":"SIAM J. Matrix Anal. Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0895-4798","issn-type":"print"},{"key":"25","doi-asserted-by":"crossref","unstructured":"S. G\u00fcttel and I. Simunec, A sketch-and-select Arnoldi process, arXiv preprint arXiv:2306.03592 (2023).","DOI":"10.1137\/23M1588007"},{"key":"26","isbn-type":"print","first-page":"1049","article-title":"Matrix oriented reduction of space-time Petrov-Galerkin variational problems","author":"Henning, Julian","year":"[2021] \\copyright2021","ISBN":"https:\/\/id.crossref.org\/isbn\/9783030558734"},{"key":"27","doi-asserted-by":"crossref","first-page":"409","DOI":"10.6028\/jres.049.044","article-title":"Methods of conjugate gradients for solving linear systems","volume":"49","author":"Hestenes, Magnus R.","year":"1952","journal-title":"J. Research Nat. Bur. Standards"},{"key":"28","unstructured":"N. Higham, The Matrix Computation Toolbox \\url{https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/2360-the-matrix-computation-toolbox}, MATLAB Central File Exchange, 2002."},{"issue":"1","key":"29","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1137\/0731012","article-title":"Krylov subspace methods for solving large Lyapunov equations","volume":"31","author":"Jaimoukha, Imad M.","year":"1994","journal-title":"SIAM J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0036-1429","issn-type":"print"},{"key":"30","doi-asserted-by":"crossref","unstructured":"D. Kressner, Memory-efficient Krylov subspace techniques for solving large-scale Lyapunov equations, 2008 IEEE International Conference on Computer-Aided Control Systems, IEEE, 2008, pp. 613\u2013618.","DOI":"10.1109\/CACSD.2008.4627370"},{"issue":"1","key":"31","doi-asserted-by":"publisher","first-page":"Paper No. e2339, 17","DOI":"10.1002\/nla.2339","article-title":"Compress-and-restart block Krylov subspace methods for Sylvester matrix equations","volume":"28","author":"Kressner, Daniel","year":"2021","journal-title":"Numer. Linear Algebra Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/1070-5325","issn-type":"print"},{"key":"32","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1017\/s0962492920000021","article-title":"Randomized numerical linear algebra: foundations and algorithms","volume":"29","author":"Martinsson, Per-Gunnar","year":"2020","journal-title":"Acta Numer.","ISSN":"https:\/\/id.crossref.org\/issn\/0962-4929","issn-type":"print"},{"issue":"2","key":"33","doi-asserted-by":"publisher","first-page":"1183","DOI":"10.1137\/23M1565413","article-title":"Fast and accurate randomized algorithms for linear systems and eigenvalue problems","volume":"45","author":"Nakatsukasa, Yuji","year":"2024","journal-title":"SIAM J. Matrix Anal. Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0895-4798","issn-type":"print"},{"issue":"3","key":"34","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1093\/imaiai\/iax011","article-title":"Universality laws for randomized dimension reduction, with applications","volume":"7","author":"Oymak, Samet","year":"2018","journal-title":"Inf. Inference","ISSN":"https:\/\/id.crossref.org\/issn\/2049-8764","issn-type":"print"},{"issue":"3","key":"35","doi-asserted-by":"publisher","first-page":"Paper No. 99, 36","DOI":"10.1007\/s10915-021-01515-x","article-title":"Matrix equation techniques for certain evolutionary partial differential equations","volume":"87","author":"Palitta, Davide","year":"2021","journal-title":"J. Sci. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0885-7474","issn-type":"print"},{"key":"36","doi-asserted-by":"crossref","unstructured":"D. Palitta, M. Schweitzer, and V. Simoncini, Sketched and truncated polynomial Krylov methods: Evaluation of matrix functions, arXiv preprint arXiv:2306.06481 (2023).","DOI":"10.1002\/nla.2596"},{"issue":"2","key":"37","doi-asserted-by":"publisher","first-page":"751","DOI":"10.1007\/s10543-015-0575-8","article-title":"Matrix-equation-based strategies for convection-diffusion equations","volume":"56","author":"Palitta, Davide","year":"2016","journal-title":"BIT","ISSN":"https:\/\/id.crossref.org\/issn\/0006-3835","issn-type":"print"},{"key":"38","doi-asserted-by":"publisher","first-page":"648","DOI":"10.1016\/j.cam.2017.08.011","article-title":"Computationally enhanced projection methods for symmetric Sylvester and Lyapunov matrix equations","volume":"330","author":"Palitta, Davide","year":"2018","journal-title":"J. Comput. Appl. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0377-0427","issn-type":"print"},{"issue":"2","key":"39","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/S0167-6911(00)00010-4","article-title":"Eigenvalue decay bounds for solutions of Lyapunov equations: the symmetric case","volume":"40","author":"Penzl, Thilo","year":"2000","journal-title":"Systems Control Lett.","ISSN":"https:\/\/id.crossref.org\/issn\/0167-6911","issn-type":"print"},{"issue":"36","key":"40","doi-asserted-by":"publisher","first-page":"13212","DOI":"10.1073\/pnas.0804869105","article-title":"A fast randomized algorithm for overdetermined linear least-squares regression","volume":"105","author":"Rokhlin, Vladimir","year":"2008","journal-title":"Proc. Natl. Acad. Sci. USA","ISSN":"https:\/\/id.crossref.org\/issn\/0027-8424","issn-type":"print"},{"key":"41","isbn-type":"print","first-page":"503","article-title":"Numerical solution of large Lyapunov equations","author":"Saad, Youcef","year":"1990","ISBN":"https:\/\/id.crossref.org\/isbn\/0817634711"},{"key":"42","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718003","volume-title":"Iterative methods for sparse linear systems","author":"Saad, Yousef","year":"2003","ISBN":"https:\/\/id.crossref.org\/isbn\/0898715342","edition":"2"},{"key":"43","doi-asserted-by":"crossref","unstructured":"T. Sarl\u00f3s, Improved approximation algorithms for large matrices via random projections, 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201906), IEEE, 2006, pp. 143\u2013152.","DOI":"10.1109\/FOCS.2006.37"},{"issue":"3","key":"44","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1137\/130912839","article-title":"Computational methods for linear matrix equations","volume":"58","author":"Simoncini, V.","year":"2016","journal-title":"SIAM Rev.","ISSN":"https:\/\/id.crossref.org\/issn\/1095-7200","issn-type":"print"},{"issue":"2","key":"45","doi-asserted-by":"publisher","first-page":"828","DOI":"10.1137\/070699378","article-title":"Convergence analysis of projection methods for the numerical solution of large Lyapunov equations","volume":"47","author":"Simoncini, V.","year":"2009","journal-title":"SIAM J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0036-1429","issn-type":"print"},{"issue":"4","key":"46","doi-asserted-by":"publisher","first-page":"711","DOI":"10.1007\/s00211-005-0603-8","article-title":"The effect of non-optimal bases on the convergence of Krylov subspace methods","volume":"100","author":"Simoncini, Valeria","year":"2005","journal-title":"Numer. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0029-599X","issn-type":"print"},{"key":"47","unstructured":"E. Timsit, L. Grigori, and O. Balabanov, Randomized orthogonal projection methods for Krylov subspace solvers, arXiv preprint arXiv:2302.07466 (2023)."},{"issue":"1-2","key":"48","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1142\/S1793536911000787","article-title":"Improved analysis of the subsampled randomized Hadamard transform","volume":"3","author":"Tropp, Joel A.","year":"2011","journal-title":"Adv. Adapt. Data Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/1793-5369","issn-type":"print"},{"issue":"2","key":"49","doi-asserted-by":"publisher","first-page":"631","DOI":"10.1137\/0913035","article-title":"Bi-CGSTAB: a fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems","volume":"13","author":"van der Vorst, H. A.","year":"1992","journal-title":"SIAM J. Sci. Statist. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0196-5204","issn-type":"print"},{"issue":"1-2","key":"50","doi-asserted-by":"publisher","first-page":"iv+157","DOI":"10.1561\/0400000060","article-title":"Sketching as a tool for numerical linear algebra","volume":"10","author":"Woodruff, David P.","year":"2014","journal-title":"Found. Trends Theor. Comput. Sci.","ISSN":"https:\/\/id.crossref.org\/issn\/1551-305X","issn-type":"print"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.ams.org\/mcom\/2025-94-354\/S0025-5718-2024-04002-4\/S0025-5718-2024-04002-4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T05:42:57Z","timestamp":1776836577000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2025-94-354\/S0025-5718-2024-04002-4\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,25]]},"references-count":50,"journal-issue":{"issue":"354","published-print":{"date-parts":[[2025,7]]}},"alternative-id":["S0025-5718-2024-04002-4"],"URL":"https:\/\/doi.org\/10.1090\/mcom\/4002","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2024,7,25]]}}}