Sketched and truncated polynomial Krylov subspace methods: Matrix Sylvester equations

Palitta, Davide; Schweitzer, Marcel; Simoncini, Valeria

doi:10.1090/mcom/4002

Sketched and truncated polynomial Krylov subspace methods: Matrix Sylvester equations
HTML articles powered by AMS MathViewer

by Davide Palitta, Marcel Schweitzer and Valeria Simoncini;

Math. Comp. 94 (2025), 1761-1792

DOI: https://doi.org/10.1090/mcom/4002

Published electronically: July 25, 2024

HTML | PDF | Request permission

Abstract:

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.

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.

References

Athanasios C. Antoulas, Approximation of large-scale dynamical systems, Advances in Design and Control, vol. 6, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2005. With a foreword by Jan C. Willems. MR 2155615, DOI 10.1137/1.9780898718713
W. E. Arnoldi, The principle of minimized iteration in the solution of the matrix eigenvalue problem, Quart. Appl. Math. 9 (1951), 17–29. MR 42792, DOI 10.1090/S0033-569X-1951-42792-9
Jonathan Baker, Mark Embree, and John Sabino, Fast singular value decay for Lyapunov solutions with nonnormal coefficients, SIAM J. Matrix Anal. Appl. 36 (2015), no. 2, 656–668. MR 3352608, DOI 10.1137/140993867
O. Balabanov and L. Grigori, Randomized block Gram–Schmidt process for solution of linear systems and eigenvalue problems, arXiv preprint arXiv:2111.14641 (2021).
O. Balabanov and L. Grigori, Randomized Gram–Schmidt process with application to GMRES, SIAM J. Sci. Comput. 44 (2022), no. 3, A1450–A1474.
Oleg Balabanov and Anthony Nouy, Randomized linear algebra for model reduction. Part I: Galerkin methods and error estimation, Adv. Comput. Math. 45 (2019), no. 5-6, 2969–3019. MR 4047024, DOI 10.1007/s10444-019-09725-6
R. H. Bartels and G. W. Stewart, Solution of the matrix equation $ax + xb= c$, Commun. ACM 15 (1972), no. 9, 820–826.
U. Baur, Low rank solution of data-sparse Sylvester equations, Numer. Linear Algebra Appl. 15 (2008), no. 9, 837–851. MR 2464171, DOI 10.1002/nla.605
Bernhard Beckermann, Image numérique, GMRES et polynômes de Faber, C. R. Math. Acad. Sci. Paris 340 (2005), no. 11, 855–860 (French, with English and French summaries). MR 2139902, DOI 10.1016/j.crma.2005.04.027
Peter Benner, Ren-Cang Li, and Ninoslav Truhar, On the ADI method for Sylvester equations, J. Comput. Appl. Math. 233 (2009), no. 4, 1035–1045. MR 2557293, DOI 10.1016/j.cam.2009.08.108
Peter Benner and Jens Saak, Numerical solution of large and sparse continuous time algebraic matrix Riccati and Lyapunov equations: a state of the art survey, GAMM-Mitt. 36 (2013), no. 1, 32–52. MR 3095913, DOI 10.1002/gamm.201310003
Dario A. Bini, Bruno Iannazzo, and Beatrice Meini, Numerical solution of algebraic Riccati equations, Fundamentals of Algorithms, vol. 9, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2012. MR 2896454
L. Burke and S. Güttel, Krylov subspace recycling with randomized sketching for matrix functions, arXiv preprint arXiv:2308.02290 (2023).
Ke Chen, Qin Li, Kit Newton, and Stephen J. Wright, Structured random sketching for PDE inverse problems, SIAM J. Matrix Anal. Appl. 41 (2020), no. 4, 1742–1770. MR 4175398, DOI 10.1137/20M1310497
Alice Cortinovis, Daniel Kressner, and Yuji Nakatsukasa, Speeding up Krylov subspace methods for computing $f(A)b$ via randomization, SIAM J. Matrix Anal. Appl. 45 (2024), no. 1, 619–633. MR 4704633, DOI 10.1137/22M1543458
Petros Drineas, Michael W. Mahoney, and S. Muthukrishnan, Subspace sampling and relative-error matrix approximation: column-based methods, Approximation, randomization and combinatorial optimization, Lecture Notes in Comput. Sci., vol. 4110, Springer, Berlin, 2006, pp. 316–326. MR 2305020, DOI 10.1007/11830924_{3}0
V. Druskin and V. Simoncini, Adaptive rational Krylov subspaces for large-scale dynamical systems, Systems Control Lett. 60 (2011), no. 8, 546–560. MR 2858340, DOI 10.1016/j.sysconle.2011.04.013
Michael Eiermann and Oliver G. Ernst, A restarted Krylov subspace method for the evaluation of matrix functions, SIAM J. Numer. Anal. 44 (2006), no. 6, 2481–2504. MR 2272603, DOI 10.1137/050633846
Andreas Frommer, Kathryn Lund, and Daniel B. Szyld, Block Krylov subspace methods for functions of matrices II: Modified block FOM, SIAM J. Matrix Anal. Appl. 41 (2020), no. 2, 804–837. MR 4101368, DOI 10.1137/19M1255847
Andreas Frommer and Valeria Simoncini, Matrix functions, Model order reduction: theory, research aspects and applications, Math. Ind., vol. 13, Springer, Berlin, 2008, pp. 275–303. MR 2497756, DOI 10.1007/978-3-540-78841-6_{1}3
L. Grasedyck, Existence of a low rank or $\scr H$-matrix approximant to the solution of a Sylvester equation, Numer. Linear Algebra Appl. 11 (2004), no. 4, 371–389. MR 2057708, DOI 10.1002/nla.366
Lars Grasedyck and Wolfgang Hackbusch, A multigrid method to solve large scale Sylvester equations, SIAM J. Matrix Anal. Appl. 29 (2007), no. 3, 870–894. MR 2338468, DOI 10.1137/040618102
L. Grigori and E. Timsit, Randomized Householder QR, Tech. report, 2023.
Stefan Güttel and Marcel Schweitzer, Randomized sketching for Krylov approximations of large-scale matrix functions, SIAM J. Matrix Anal. Appl. 44 (2023), no. 3, 1073–1095. MR 4619373, DOI 10.1137/22M1518062
S. Güttel and I. Simunec, A sketch-and-select Arnoldi process, arXiv preprint arXiv:2306.03592 (2023).
Julian Henning, Davide Palitta, Valeria Simoncini, and Karsten Urban, Matrix oriented reduction of space-time Petrov-Galerkin variational problems, Numerical mathematics and advanced applications—ENUMATH 2019, Lect. Notes Comput. Sci. Eng., vol. 139, Springer, Cham, [2021] ©2021, pp. 1049–1057. MR 4266584
Magnus R. Hestenes and Eduard Stiefel, Methods of conjugate gradients for solving linear systems, J. Research Nat. Bur. Standards 49 (1952), 409–436 (1953). MR 60307, DOI 10.6028/jres.049.044
N. Higham, The Matrix Computation Toolbox https://www.mathworks.com/matlabcentral/fileexchange/2360-the-matrix-computation-toolbox, MATLAB Central File Exchange, 2002.
Imad M. Jaimoukha and Ebrahim M. Kasenally, Krylov subspace methods for solving large Lyapunov equations, SIAM J. Numer. Anal. 31 (1994), no. 1, 227–251. MR 1259974, DOI 10.1137/0731012
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–618.
Daniel Kressner, Kathryn Lund, Stefano Massei, and Davide Palitta, Compress-and-restart block Krylov subspace methods for Sylvester matrix equations, Numer. Linear Algebra Appl. 28 (2021), no. 1, Paper No. e2339, 17. MR 4184095, DOI 10.1002/nla.2339
Per-Gunnar Martinsson and Joel A. Tropp, Randomized numerical linear algebra: foundations and algorithms, Acta Numer. 29 (2020), 403–572. MR 4189294, DOI 10.1017/s0962492920000021
Yuji Nakatsukasa and Joel A. Tropp, Fast and accurate randomized algorithms for linear systems and eigenvalue problems, SIAM J. Matrix Anal. Appl. 45 (2024), no. 2, 1183–1214. MR 4760964, DOI 10.1137/23M1565413
Samet Oymak and Joel A. Tropp, Universality laws for randomized dimension reduction, with applications, Inf. Inference 7 (2018), no. 3, 337–446. MR 3858331, DOI 10.1093/imaiai/iax011
Davide Palitta, Matrix equation techniques for certain evolutionary partial differential equations, J. Sci. Comput. 87 (2021), no. 3, Paper No. 99, 36. MR 4260433, DOI 10.1007/s10915-021-01515-x
D. Palitta, M. Schweitzer, and V. Simoncini, Sketched and truncated polynomial Krylov methods: Evaluation of matrix functions, arXiv preprint arXiv:2306.06481 (2023).
Davide Palitta and Valeria Simoncini, Matrix-equation-based strategies for convection-diffusion equations, BIT 56 (2016), no. 2, 751–776. MR 3503262, DOI 10.1007/s10543-015-0575-8
Davide Palitta and Valeria Simoncini, Computationally enhanced projection methods for symmetric Sylvester and Lyapunov matrix equations, J. Comput. Appl. Math. 330 (2018), 648–659. MR 3717618, DOI 10.1016/j.cam.2017.08.011
Thilo Penzl, Eigenvalue decay bounds for solutions of Lyapunov equations: the symmetric case, Systems Control Lett. 40 (2000), no. 2, 139–144. MR 1829181, DOI 10.1016/S0167-6911(00)00010-4
Vladimir Rokhlin and Mark Tygert, A fast randomized algorithm for overdetermined linear least-squares regression, Proc. Natl. Acad. Sci. USA 105 (2008), no. 36, 13212–13217. MR 2443725, DOI 10.1073/pnas.0804869105
Youcef Saad, Numerical solution of large Lyapunov equations, Signal processing, scattering and operator theory, and numerical methods (Amsterdam, 1989) Progr. Systems Control Theory, vol. 5, Birkhäuser Boston, Boston, MA, 1990, pp. 503–511. MR 1115480
Yousef Saad, Iterative methods for sparse linear systems, 2nd ed., Society for Industrial and Applied Mathematics, Philadelphia, PA, 2003. MR 1990645, DOI 10.1137/1.9780898718003
T. Sarlós, Improved approximation algorithms for large matrices via random projections, 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06), IEEE, 2006, pp. 143–152.
V. Simoncini, Computational methods for linear matrix equations, SIAM Rev. 58 (2016), no. 3, 377–441. MR 3532794, DOI 10.1137/130912839
V. Simoncini and V. Druskin, Convergence analysis of projection methods for the numerical solution of large Lyapunov equations, SIAM J. Numer. Anal. 47 (2009), no. 2, 828–843. MR 2485434, DOI 10.1137/070699378
Valeria Simoncini and Daniel B. Szyld, The effect of non-optimal bases on the convergence of Krylov subspace methods, Numer. Math. 100 (2005), no. 4, 711–733. MR 2194591, DOI 10.1007/s00211-005-0603-8
E. Timsit, L. Grigori, and O. Balabanov, Randomized orthogonal projection methods for Krylov subspace solvers, arXiv preprint arXiv:2302.07466 (2023).
Joel A. Tropp, Improved analysis of the subsampled randomized Hadamard transform, Adv. Adapt. Data Anal. 3 (2011), no. 1-2, 115–126. MR 2835584, DOI 10.1142/S1793536911000787
H. A. van der Vorst, Bi-CGSTAB: a fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems, SIAM J. Sci. Statist. Comput. 13 (1992), no. 2, 631–644. MR 1149111, DOI 10.1137/0913035
David P. Woodruff, Sketching as a tool for numerical linear algebra, Found. Trends Theor. Comput. Sci. 10 (2014), no. 1-2, iv+157. MR 3285427, DOI 10.1561/0400000060

AMS Website Down

Mathematics of Computation

Sketched and truncated polynomial Krylov subspace methods: Matrix Sylvester equations
HTML articles powered by AMS MathViewer

Abstract: