Inexact methods for the low rank solution to large scale Lyapunov equations. (English) Zbl 1455.65050

Summary: The rational Krylov subspace method (RKSM) and the low-rank alternating directions implicit (LR-ADI) iteration are established numerical tools for computing low-rank solution factors of large-scale Lyapunov equations. In order to generate the basis vectors for the RKSM, or extend the low-rank factors within the LR-ADI method, the repeated solution to a shifted linear system of equations is necessary. For very large systems this solve is usually implemented using iterative methods, leading to inexact solves within this inner iteration (and therefore to “inexact methods”). We will show that one can terminate this inner iteration before full precision has been reached and still obtain very good accuracy in the final solution to the Lyapunov equation. In particular, for both the RKSM and the LR-ADI method we derive theory for a relaxation strategy (e.g. increasing the solve tolerance of the inner iteration, as the outer iteration proceeds) within the iterative methods for solving the large linear systems. These theoretical choices involve unknown quantities, therefore practical criteria for relaxing the solution tolerance within the inner linear system are then provided. The theory is supported by several numerical examples, which show that the total amount of work for solving Lyapunov equations can be reduced significantly.


65F45 Numerical methods for matrix equations
15A24 Matrix equations and identities
65F55 Numerical methods for low-rank matrix approximation; matrix compression


Algorithm 432; RADI
Full Text: DOI arXiv


[1] Ahmad, MI; Szyld, DB; van Gijzen, MB, Preconditioned multishift BiCG for \(H_2\)-optimal model reduction, SIAM J. Matrix Anal. Appl., 38, 2, 401-424 (2017) · Zbl 1365.65080
[2] Antoulas, AC, Approximation of Large-Scale Dynamical Systems (2005), Philadelphia, PA: SIAM, Philadelphia, PA · Zbl 1112.93002
[3] Baker, J.; Embree, M.; Sabino, J., Fast singular value decay for Lyapunov solutions with nonnormal coefficients, SIAM J. Matrix Anal. Appl., 36, 2, 656-668 (2015) · Zbl 1320.15011
[4] Bartels, RH; Stewart, GW, Solution of the matrix equation \({AX}+{XB}={C}\): algorithm 432, Commun. ACM, 15, 820-826 (1972) · Zbl 1372.65121
[5] Beckermann, B.; Townsend, A., On the singular values of matrices with displacement structure, SIAM J. Matrix Anal. Appl., 38, 4, 1227-1248 (2017) · Zbl 1386.15024
[6] Benner, P.; Bujanović, Z.; Kürschner, P.; Saak, J., A numerical comparison of solvers for large-scale, continuous-time algebraic Riccati equations and LQR problems, SIAM J. Sci. Comput., 42, 2, A957-A996 (2020) · Zbl 1437.65021
[7] Benner, P.; Bujanović, Z.; Kürschner, P.; Saak, J., RADI: a low-rank ADI-type algorithm for large scale algebraic Riccati equations, Numer. Math., 138, 2, 301-330 (2018) · Zbl 1385.65035
[8] Benner, P.; Heinkenschloss, M.; Saak, J.; Weichelt, HK, An inexact low-rank Newton-ADI method for large-scale algebraic Riccati equations, Appl. Numer. Math., 108, 125-142 (2016) · Zbl 1346.65017
[9] Benner, P.; Kürschner, P., Computing real low-rank solutions of Sylvester equations by the factored ADI method, Comput. Math. Appl., 67, 9, 1656-1672 (2014) · Zbl 1364.65093
[10] Benner, P.; Kürschner, P.; Saak, J., An improved numerical method for balanced truncation for symmetric second order systems, Math. Comput. Model. Dyn. Sys., 19, 6, 593-615 (2013) · Zbl 1305.93043
[11] Benner, P.; Kürschner, P.; Saak, J., Efficient Handling of complex shift parameters in the low-rank Cholesky factor ADI method, Numer. Algorithms, 62, 2, 225-251 (2013) · Zbl 1267.65047
[12] Benner, P.; Kürschner, P.; Saak, J., Self-generating and efficient shift parameters in ADI methods for large Lyapunov and Sylvester equations, Electron. Trans. Numer. Anal., 43, 142-162 (2014) · Zbl 1312.65068
[13] Benner, P.; Li, R-C; Truhar, N., On the ADI method for Sylvester equations, J. Comput. Appl. Math., 233, 4, 1035-1045 (2009) · Zbl 1176.65050
[14] Benner, P.; Saak, J., Numerical solution of large and sparse continuous time algebraic matrix Riccati and Lyapunov equations: a state of the art survey, GAMM Mitteilungen, 36, 1, 32-52 (2013) · Zbl 1279.65044
[15] Bergamaschi, L.; Martínez, Á., Two-stage spectral preconditioners for iterative eigensolvers, Numer. Linear Algebra Appl., 24, 3, e2084 (2017) · Zbl 1424.65038
[16] Berljafa, M.; Güttel, S., Generalized rational Krylov decompositions with an application to rational approximation, SIAM J. Matrix Anal. Appl., 36, 2, 894-916 (2015) · Zbl 1319.65028
[17] Bouras, A.; Frayssé, V., Inexact matrix-vector products in Krylov methods for solving linear systems: a relaxation strategy, SIAM J. Matrix Anal. Appl., 26, 3, 660-678 (2005) · Zbl 1075.65041
[18] Canuto, C.; Simoncini, V.; Verani, M., On the decay of the inverse of matrices that are sum of Kronecker products, Linear Algebra Appl., 452, 21-39 (2014) · Zbl 1291.65144
[19] Crouzeix, M.; Palencia, C., The numerical range is a \((1+\sqrt{2})\)-spectral set, SIAM J. Matrix Anal. Appl., 38, 2, 649-655 (2017) · Zbl 1368.47006
[20] Druskin, V.; Knizhnerman, LA; Simoncini, V., Analysis of the rational Krylov subspace and ADI methods for solving the Lyapunov equation, SIAM J. Numer. Anal., 49, 1875-1898 (2011) · Zbl 1244.65060
[21] Druskin, V.; Simoncini, V., Adaptive rational Krylov subspaces for large-scale dynamical systems, Syst. Control Lett., 60, 8, 546-560 (2011) · Zbl 1236.93035
[22] Freitag, M.A., Spence, A.: Convergence theory for inexact inverse iteration applied to the generalised nonsymmetric eigenproblem. Electron. Trans. Numer. Anal. 28, 40-64 (2007/08) · Zbl 1171.65025
[23] Freitag, MA; Spence, A., Shift-invert Arnoldi’s method with preconditioned iterative solves, SIAM J. Matrix Anal. Appl., 31, 3, 942-969 (2009) · Zbl 1204.65034
[24] Gaaf, SW; Simoncini, V., Approximating the leading singular triplets of a large matrix function, Appl. Numer. Math., 113, 26-43 (2017) · Zbl 1355.65062
[25] Grasedyck, L., Existence of a low rank or \({\cal{H}} \)-matrix approximant to the solution of a Sylvester equation, Numer. Linear Algebra Appl., 11, 4, 371-389 (2004) · Zbl 1164.65381
[26] Güttel, S.: Rational Krylov methods for operator functions. Ph.D. thesis, Technische Universität Bergakademie Freiberg, Germany. http://eprints.ma.man.ac.uk/2586/ (2010)
[27] Güttel, S., Rational Krylov approximation of matrix functions: numerical methods and optimal pole selection, GAMM-Mitteilungen, 36, 1, 8-31 (2013) · Zbl 1292.65043
[28] Jaimoukha, IM; Kasenally, EM, Krylov subspace methods for solving large Lyapunov equations, SIAM J. Numer. Anal., 31, 227-251 (1994) · Zbl 0798.65060
[29] Kressner, D.; Massei, S.; Robol, L., Low-rank updates and a divide-and-conquer method for linear matrix equations, SIAM J. Sci. Comput., 41, 2, A848-A876 (2019) · Zbl 1448.65034
[30] Kürschner, P.: Efficient low-rank solution of large-scale matrix equations. Dissertation, Otto-von-Guericke-Universität, Magdeburg, Germany. http://hdl.handle.net/11858/00-001M-0000-0029-CE18-2 (2016)
[31] Lehoucq, RB; Meerbergen, K., Using generalized Cayley transformations within an inexact rational Krylov sequence method, SIAM J. Matrix Anal. Appl., 20, 1, 131-148 (1998) · Zbl 0931.65035
[32] Li, J.-R.:Model reduction of large linear systems via low rank system Gramians. Ph.D. thesis, Massachusettes Institute of Technology (2000)
[33] Li, J-R; White, J., Low rank solution of Lyapunov equations, SIAM J. Matrix Anal. Appl., 24, 1, 260-280 (2002) · Zbl 1016.65024
[34] Opmeer, M.; Reis, T.; Wollner, W., Finite-rank ADI iteration for operator Lyapunov equations, SIAM J. Control Optim., 51, 5, 4084-4117 (2013) · Zbl 1279.93022
[35] Palitta, D.; Simoncini, V., Numerical methods for large-scale Lyapunov equations with symmetric banded data, SIAM J. Sci. Comput., 40, 5, A3581-A3608 (2018) · Zbl 1416.65119
[36] Penzl, T., A cyclic low rank Smith method for large sparse Lyapunov equations, SIAM J. Sci. Comput., 21, 4, 1401-1418 (2000) · Zbl 0958.65052
[37] Ruhe, Axel, The rational Krylov algorithm for nonsymmetric eigenvalue problems. III: complex shifts for real matrices, BIT, 34, 165-176 (1994) · Zbl 0810.65032
[38] Saad, Y.; Kaashoek, MA; van Schuppen, JH; Ran, ACM, Numerical solution of large Lyapunov equation, Signal Processing, 503-511 (1990), Basel: Birkhäuser, Basel
[39] Saak, J.: Efficient numerical solution of large scale algebraic matrix equations in PDE control and model order reduction. Ph.D. thesis, TU Chemnitz. http://nbn-resolving.de/urn:nbn:de:bsz:ch1-200901642 (2009)
[40] Sabino, J.: Solution of large-scale Lyapunov equations via the block modified Smith method. Ph.D. thesis, Rice University, Houston, TX. http://www.caam.rice.edu/tech_reports/2006/TR06-08.pdf (2007)
[41] Shank, SD; Simoncini, V.; Szyld, DB, Efficient low-rank solution of generalized Lyapunov equations, Numer. Math., 134, 327-342 (2015) · Zbl 1348.65078
[42] Simoncini, V., Variable accuracy of matrix-vector products in projection methods for eigencomputation, SIAM J. Numer. Anal., 43, 3, 1155-1174 (2005) · Zbl 1093.65037
[43] Simoncini, V., A new iterative method for solving large-scale Lyapunov matrix equations, SIAM J. Sci. Comput., 29, 3, 1268-1288 (2007) · Zbl 1146.65038
[44] Simoncini, V., Analysis of the rational Krylov subspace projection method for large-scale algebraic Riccati equations, SIAM J. Matrix Anal. Appl., 37, 4, 1655-1674 (2016) · Zbl 06655499
[45] Simoncini, V., Computational methods for linear matrix equations, SIAM Rev., 58, 3, 377-441 (2016) · Zbl 1386.65124
[46] Simoncini, V.; Eldén, L., Inexact Rayleigh quotient-type methods for eigenvalue computations, BIT Numer. Math., 42, 1, 159-182 (2002) · Zbl 1003.65033
[47] Simoncini, V.; Szyld, DB, Theory of inexact Krylov subspace methods and applications to scientific computing, SIAM J. Sci. Comput., 25, 2, 454-477 (2003) · Zbl 1048.65032
[48] Simoncini, V.; Szyld, DB; Monsalve, M., On two numerical methods for the solution of large-scale algebraic Riccati equations, IMA J. Numer. Anal., 34, 3, 904-920 (2014) · Zbl 1298.65083
[49] Soodhalter, K., A block MINRES algorithm based on the banded Lanczos method, Numer. Algorithms, 69, 473-494 (2015) · Zbl 1320.65051
[50] Sun, K.: Model order reduction and domain decomposition for large-scale dynamical systems. Ph.D. thesis, Rice University, Houston. http://search.proquest.com/docview/304507831 (2008)
[51] Truhar, N.; Veselić, K., Bounds on the trace of a solution to the Lyapunov equation with a general stable matrix, Syst. Control Lett., 56, 7-8, 493-503 (2007) · Zbl 1117.93066
[52] Truhar, N.; Veselić, K., An efficient method for estimating the optimal dampers’ viscosity for linear vibrating systems using Lyapunov equation, SIAM J. Matrix Anal. Appl., 31, 1, 18-39 (2009) · Zbl 1303.70021
[53] van den Eshof, J.; Sleijpen, G., Inexact Krylov subspace methods for linear systems, SIAM J. Matrix Anal. Appl., 26, 1, 125-153 (2004) · Zbl 1079.65036
[54] Wachspress, EL, The ADI Model Problem (2013), New York: Springer, New York · Zbl 1277.65022
[55] Wolf, T.; Panzer, HK-F, The ADI iteration for Lyapunov equations implicitly performs \({\cal{H}}_2\) pseudo-optimal model order reduction, Int. J. Control, 89, 3, 481-493 (2016) · Zbl 1332.93142
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.