From low-rank approximation to a rational Krylov subspace method for the Lyapunov equation. (English) Zbl 1327.65064
Summary: We propose a new method for the approximate solution of the Lyapunov equation with rank-1 right-hand side, which is based on an extended rational Krylov subspace approximation with adaptively computed shifts. The shift selection is obtained from the connection between the Lyapunov equation, solution of systems of linear ODEs, and an alternating least squares method for low-rank approximation. We provide numerical comparison of our method with other well-established techniques for the approximation solution of the Lyapunov equation on different problems.
MSC:
| 65F10 | Iterative numerical methods for linear systems |
| 65F30 | Other matrix algorithms (MSC2010) |
| 15A06 | Linear equations (linear algebraic aspects) |
| 93B40 | Computational methods in systems theory (MSC2010) |
References:
| [1] | Z. Bai, {\it Krylov subspace techniques for reduced-order modeling of large-scale dynamical systems}, Appl. Numer. Math., 43 (2002), pp. 9-44. · Zbl 1012.65136 |
| [2] | C. A. Beattie and S. Gugercin, {\it Krylov-based minimization for optimal \(\mathcal{H}^2\) model reduction}, in 46th IEEE Conference on Decision and Control, IEEE, Piscataway, NJ, 2007, pp. 4385-4390. |
| [3] | W. N. Bell, L. N. Olson, and J. B. Schroder, {\it PyAMG: Algebraic Multigrid Solvers in Python v}2.0, http://www.pyamg.org (2011). |
| [4] | P. Benner, P. Kürschner, and J. Saak, {\it Self-generating and efficient shift parameters in ADI methods for large Lyapunov and Sylvester equations}, GAMM-Mitt., 17 (2013), pp. 123-143. · Zbl 1312.65068 |
| [5] | P. Benner, J.-R. Li, and T. Penzl, {\it Numerical solution of large-scale Lyapunov equations, Riccati equations, and linear-quadratic optimal control problems}, Numer. Linear Algebra, 15 (2008), pp. 755-777. · Zbl 1212.65245 |
| [6] | T. Damm, {\it Direct methods and ADI-preconditioned Krylov subspace methods for generalized Lyapunov equations}, Numer. Linear Algebra, 15 (2008), pp. 853-871. · Zbl 1212.65175 |
| [7] | V. Druskin and L. Knizhnerman, {\it Extended Krylov subspaces: Approximation of the matrix square root and related functions}, SIAM J. Matrix Anal. Appl., 19 (1998), pp. 755-771. · Zbl 0912.65022 |
| [8] | V. Druskin, C. Lieberman, and M. Zaslavsky, {\it On adaptive choice of shifts in rational Krylov subspace reduction of evolutionary problems}, SIAM J. Sci. Comput., 32 (2010), pp. 2485-2496. · Zbl 1221.65255 |
| [9] | V. Druskin and V. Simoncini, {\it Adaptive rational Krylov subspaces for large-scale dynamical systems}, Systems Control Lett., 60 (2011), pp. 546-560. · Zbl 1236.93035 |
| [10] | V. Druskin, V. Simoncini, and M. Zaslavsky, {\it Adaptive tangential interpolation in rational Krylov subspaces for MIMO dynamical systems}, SIAM J. Matrix Anal. Appl., 35 (2014), pp. 476-498. · Zbl 1314.65085 |
| [11] | G. Flagg, C. Beattie, and S. Gugercin, {\it Convergence of the iterative rational Krylov algorithm}, Systems Control. Lett., 61 (2012), pp. 688-691. · Zbl 1401.93051 |
| [12] | S. Gugercin, {\it An iterative rational Krylov algorithm (IRKA) for optimal \(\mathcal{H}^2\) model reduction}, in Householder Symposium XVI, Seven Springs Mountain Resort, PA, 2005. |
| [13] | S. Gugercin, A. C. Antoulas, and C. Beattie, {\it \(\mathcal{H}^2\) model reduction for large-scale linear dynamical systems}, SIAM J. Matrix Anal. Appl., 30 (2008), pp. 609-638. · Zbl 1159.93318 |
| [14] | S. Gugercin, D. C. Sorensen, and A. C. Antoulas, {\it A modified low-rank Smith method for large-scale Lyapunov equations}, Numer Algorithms, 32 (2003), pp. 27-55. · Zbl 1034.93020 |
| [15] | N. J. Higham, {\it Functions of Matrices: Theory and Computation}, SIAM, Philadelphia, 2008. · Zbl 1167.15001 |
| [16] | T. Hinamoto, {\it \(2\)-d Lyapunov equation and filter design based on the Fornasini-Marchesini second model}, IEEE Trans. Circuits Syst. I, Fund. Theory Appl., 40 (1993), pp. 102-110. · Zbl 0825.93827 |
| [17] | M. Hochbruck and C. Lubich, {\it On Krylov subspace approximations to the matrix exponential operator}, SIAM J. Numer. Anal., 34 (1997), pp. 1911-1925. · Zbl 0888.65032 |
| [18] | M. Hochbruck and G. Starke, {\it Preconditioned Krylov subspace methods for Lyapunov matrix equations}, SIAM J. Matrix Anal. Appl., 16 (1995), pp. 156-171. · Zbl 0827.65048 |
| [19] | I. M. Jaimoukha and E. M. Kasenally, {\it Krylov subspace methods for solving large Lyapunov equations}, SIAM J. Numer. Anal., 31 (1994), pp. 227-251. · Zbl 0798.65060 |
| [20] | K. Jbilou, {\it ADI preconditioned Krylov methods for large Lyapunov matrix equations}, Linear Algebra Appl., 432 (2010), pp. 2473-2485. · Zbl 1189.65078 |
| [21] | K. Jbilou and A. Riquet, {\it Projection methods for large Lyapunov matrix equations}, Linear Algebra Appl., 415 (2006), pp. 344-358. · Zbl 1094.65039 |
| [22] | A. J. Laub, {\it A schur method for solving algebraic Riccati equations}, IEEE Trans. Automat. Control, 24 (1979), pp. 913-921. · Zbl 0424.65013 |
| [23] | V. I. Lebedev, {\it On a Zolotarev problem in the method of alternating directions}, USSR Comput. Math. Math. Phys., 17 (1977), pp. 58-76. · Zbl 0379.65032 |
| [24] | J.-R. Li, F. Wang, and J. K. White, {\it An efficient Lyapunov equation-based approach for generating reduced-order models of interconnect}, in Proceedings of the 36th annual ACM/IEEE Design Automation Conference, ACM, New York, 1999, pp. 1-6. |
| [25] | J.-R. Li and J. White, {\it Low rank solution of Lyapunov equations}, SIAM J. Matrix Anal. Appl., 24 (2002), pp. 260-280. · Zbl 1016.65024 |
| [26] | A. Lu and E. L. Wachspress, {\it Solution of Lyapunov equations by alternating direction implicit iteration}, Comput. Math. Appl., 21 (1991), pp. 43-58. · Zbl 0724.65041 |
| [27] | C. C. K. Mikkelsen, {\it Any Positive Residual Curve is Possible for the Arnoldi Method for Lyapunov Matrix Equations}, Technical report UMINF 10.03, Department of Computing Science and HPC2N, Ume\aa University, Ume\aa, Sweden, 2010. |
| [28] | T. Penzl, {\it A cyclic low-rank Smith method for large sparse Lyapunov equations}, SIAM J. Sci. Comput., 21 (1999), pp. 1401-1418. · Zbl 0958.65052 |
| [29] | J.-B. Pomet and L. Praly, {\it Adaptive nonlinear regulation: Estimation from the Lyapunov equation}, IEEE Trans. Automat. Control, 37 (1992), pp. 729-740. · Zbl 0755.93071 |
| [30] | Y. Saad, {\it Numerical Solution of Large Lyapunov Equations}, Technical Report NASA-CR-180359, Research Institute for Advanced Computer Science, NASA Ames Research Center, Moffet Field, CA, 1989. |
| [31] | Y. Saad, {\it Overview of Krylov Subspace Methods with Applications to Control Problems}, Technical Report NASA-CR-188842, Research Institute for Advanced Computer Science, NASA Ames Research Center, Moffet Field, CA, 1989. · Zbl 0722.93028 |
| [32] | Y. Saad, {\it Iterative Methods for Sparse Linear Systems}, 2nd ed., SIAM, Philadelphia, 2003. · Zbl 1031.65046 |
| [33] | J. M. Sanches, J. C. Nascimento, and J. S. Marques, {\it Medical image noise reduction using the Sylvester-Lyapunov equation}, IEEE Trans. Image Process., 17 (2008), pp. 1522-1539. · Zbl 1279.94034 |
| [34] | V. Simoncini, {\it A new iterative method for solving large-scale Lyapunov matrix equations}, SIAM J. Sci. Comput., 29 (2007), pp. 1268-1288. · Zbl 1146.65038 |
| [35] | V. Simoncini, {\it Computational Methods for Linear Matrix Equations}, Technical report, Università di Bologna, Bologna, Italy, 2013. · Zbl 1386.65124 |
| [36] | V. Simoncini and V. Druskin, {\it Convergence analysis of projection methods for the numerical solution of large Lyapunov equations}, SIAM J. Numer. Anal., 47 (2009), pp. 828-843. · Zbl 1195.65058 |
| [37] | D. Sorensen and A. Antoulas, {\it The Sylvester equation and approximate balanced reduction}, Linear Algebra Appl., 351 (2002), pp. 671-700. · Zbl 1023.93012 |
| [38] | T. Stykel and V. Simoncini, {\it Krylov subspace methods for projected Lyapunov equations}, Appl. Numer. Math., 62 (2012), pp. 35-50. · Zbl 1258.65044 |
| [39] | B. Vandereycken, {\it Riemannian and Multilevel Optimization for Rank-Constrained Matrix Problems}, Ph.D. thesis, Katholieke Universiteit Leuven, Belgium, 2010. |
| [40] | B. Vandereycken and S. Vandewalle, {\it A Riemannian optimization approach for computing low-rank solutions of Lyapunov equations}, SIAM J. Matrix Anal. Appl., 31 (2010), pp. 2553-2579. · Zbl 1221.65108 |
| [41] | K. Veselić, {\it Damped Oscillations of Linear Systems: A Mathematical Introduction}, Lecture Notes in Math. 2023, Springer-Verlag, Berlin, 2011. · Zbl 1232.37004 |
| [42] | E. L. Wachspress, {\it Iterative solution of the Lyapunov matrix equation}, Appl. Math. Lett., 1 (1988), pp. 87-90. · Zbl 0631.65037 |
| [43] | Y. Zhou and D. Sorensen, {\it Approximate implicit subspace iteration with alternating directions for LTI system model reduction}, Numer. Linear Algebra Appl., 15 (2008), pp. 873-886. · Zbl 1212.65258 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
