On Hessenberg type methods for low-rank Lyapunov matrix equations. (English) Zbl 1405.65040
Summary: The Hessenberg process can be seen as an alternative to the well-known Arnoldi and Lanczos processes. Block and global versions of the Hessenberg process were used for solving linear systems with multiple right-hand sides and large Sylvester matrix equations. In this work, we describe two new Hessenberg based methods for obtaining approximate solutions to low-rank Lyapunov matrix equations. The first one is based on a Ruhe variant of the block Hessenberg process and belongs to the class of block Krylov solvers. The second one is a matrix Krylov solver and uses the global Hessenberg process. The numerical comparisons we have made show that solving the Lyapunov equation via the global Hessenberg process gives better results compared to the use of the block Hessenberg process.
MSC:
| 65F10 | Iterative numerical methods for linear systems |
| 65F30 | Other matrix algorithms (MSC2010) |
Keywords:
block Krylov subspace; matrix Krylov subspace; block Hessenberg process; global Hessenberg process; low-rank Lyapunov matrix equationsReferences:
| [1] | M. Addam, M. Heyouni and H. Sadok, The block Hessenberg process for matrix equations, Electron. Trans. Numer. Anal. 46 (2017), 460-473. · Zbl 1392.65041 |
| [2] | S. Agoujil, A. Bentbib, K. Jbilou and El M. Sadek, Minimization method for large Sylvester matrix problems, Electron. Trans. Numer. Anal. 43 (2014), 45-59. · Zbl 1302.65096 |
| [3] | A. C. Antoulas, Approximation of Large-Scale Dynamical Systems, Adv. Des. Control, SIAM, Philadelphia, 2005. · Zbl 1112.93002 |
| [4] | R. H. Bartels and G. W. Stewart, Solution of the matrix equation AX + XB = C, Comm. ACM 15 (1972), 820-826. · Zbl 1372.65121 |
| [5] | U. Baur and P. Benner, Factorized solution of Lyapunov equations based on hierarchical matrix arithmetic, Computing 78 (2006), 211-234. · Zbl 1111.65039 |
| [6] | P. Benner, Control theory, in: Handbook of Linear Algebra, L. Hogben (ed.), Chapman & Hall/CRC, 2007, 57-1-57-18. · Zbl 1122.15001 |
| [7] | P. Benner, E. S. Quintana-Ort´ı and G. Quintana-Ort´ı, Solving stable Sylvester equations via rational iterative schemes, J. Sci. Comput. 28 (2006), 51-83. · Zbl 1098.65041 |
| [8] | A. Bentbib, K. Jbilou and El M. Sadek, On some Krylov subspace based methods for large-scale nonsymmetric algebraic Riccati problems, Computers Math. Appl. 70 (2015), 2555-2565. · Zbl 1443.65054 |
| [9] | R. F. Boisvert, R. Pozo, K. Remington, R. F. Barrett and J. J. Dongarra, Matrix market: a web eesource for test matrix collections, math.nist.gov/MatrixMarket/. |
| [10] | A. Bouhamidi and K. Jbilou, On the convergence of inexact Newton methods for discrete-time algebraic Riccati equations, Linear Algebra Appl. 439 (2013), 2057-2069. · Zbl 1305.65143 |
| [11] | R. Bouyouli, K. Jbilou, R. Sadaka and H. Sadok, Convergence properties of some block Krylov subspace methods for multiple linear systems, J. Comput. Appl. Math. 196 (2006), 498-511. · Zbl 1100.65024 |
| [12] | C. Brezinski, Projection Methods of Systems of Equations, North-Holland, Amsterdam, 1997. · Zbl 0889.65023 |
| [13] | C. Brezinski, Projection methods for linear systems, J. Comput. Appl. Math. 77 (1997), 35-51. · Zbl 0867.65009 |
| [14] | C. Brezinski, Computational Aspects of Linear Control, Kluwer, Dordrecht, 2002. · Zbl 1010.93003 |
| [15] | B. N. Datta and Y. Saad, Arnoldi methods for large Sylvester-like observer matrix equations, and an associated algorithm for partial spectrum assignment, Linear Algebra Appl. 154-156 (1991), 225-244. · Zbl 0734.65037 |
| [16] | B. N. Datta, Numerical Methods for Linear Control Systems. Design and Analysis, Elsevier, 2004. · Zbl 1079.65072 |
| [17] | T. A. Davis and Y. Hu, The University of Florida sparse matrix collection, ACM Trans. Math. Software 38 (2011), art. 1, 25 pp.; www.cise.ufl.edu/research/sparse/ matrices/ · Zbl 1365.65123 |
| [18] | A. El Guennouni, K. Jbilou and A. J. Riquet, Block Krylov subspace methods for solving large Sylvester equations, Numer. Algorithms 29 (2006), 75-96. · Zbl 0992.65040 |
| [19] | H. Elman, D. Furnival and C. Powell, H(div) preconditioning for a mixed finite element formulation of the diffusion problem with random data, Math. Comput. 79 (2010), 733-760. · Zbl 1216.65155 |
| [20] | K. Glover, D. J. N. Limebeer, J. C. Doyle, E. M. Kasenally and M. G. Safonov, A characterisation of all solutions to the four block general distance problem, SIAM J. Control Optim. 29 (1991), 283-324. · Zbl 0736.93015 |
| [21] | G. H. Golub, S. Nash and C. Van Loan, A Hessenberg-Schur method for the problem AX + XB = C, IEEE Trans. Automat. Control 24 (1979), 909-913. · Zbl 0421.65022 |
| [22] | S. Gugercin, D. C. Sorensen and A. C. Antoulas, A modified low-rank Smith method for large-scale Lyapunov equations, Numer. Algorithms 32 (2003), 27-55. · Zbl 1034.93020 |
| [23] | M. Heyouni, The global Hessenberg and CMRH methods for linear systems with multiple right-hand sides, Numer. Algorithms 26 (2001), 317-332. · Zbl 0979.65025 |
| [24] | M. Heyouni, Extended Arnoldi methods for large low-rank Sylvester matrix equations, Appl. Numer. Math. 60 (2010), 1171-1182. · Zbl 1210.65093 |
| [25] | M. Heyouni and A. Essai, Matrix Krylov subspace methods for linear systems with multiple right-hand sides, Numer. Algorithms 40 (2005), 137-156. · Zbl 1087.65028 |
| [26] | M. Heyouni and K. Jbilou, Matrix Krylov subspace methods for large scale model reduction problems, Appl. Math. Comput. 181 (2006), 1215-1228. · Zbl 1115.65042 |
| [27] | M. Heyouni and H. Sadok, A new implementation of the CMRH method for solving dense linear systems, J. Comput. Appl. Math. 213 (2008), 387-399. · Zbl 1136.65036 |
| [28] | R. A. Horn and C. R. Johnson, Topics in Matrix Analysis, Cambridge Univ. Press, Cambridge, 1991. · Zbl 0729.15001 |
| [29] | I. M. Jaimoukha and E. M. Kasenally, Krylov subspace methods for solving large Lyapunov equations, SIAM J. Numer. Anal. 31 (1994), 227-251. · Zbl 0798.65060 |
| [30] | K. Jbilou, ADI preconditioned Krylov methods for large Lyapunov matrix equations, Linear Algebra Appl. 432 (2010), 2473-2485. · Zbl 1189.65078 |
| [31] | K. Jbilou, A. Messaoudi and H. Sadok, Global FOM and GMRES algorithms for matrix equations, Appl. Numer. Math. 31 (1999), 49-63. · Zbl 0935.65024 |
| [32] | K. Jbilou and A. J. Riquet, Projection methods for large Lyapunov matrix equations, Linear Algebra Appl. 415 (2006), 344-358. · Zbl 1094.65039 |
| [33] | P. Lancaster and L. Rodman, The Algebraic Riccati Equations, Clarendon Press, Oxford, 1995. · Zbl 0836.15005 |
| [34] | P. Lancaster and M. Tismenetsky, The Theory of Matrices, 2nd ed., Academic Press, Orlando, FL, 1985. · Zbl 0558.15001 |
| [35] | J. R. Li and J. White, Low rank solution of Lyapunov equations, SIAM J. Matrix Anal. Appl. 24 (2002), 260-280. · Zbl 1016.65024 |
| [36] | A. Lu and E. Wachspress, Solution of Lyapunov equations by alternating direction implicit iteration, Comput. Math. Appl. 21 (1991), 43-58. · Zbl 0724.65041 |
| [37] | Oberwolfach model reduction benchmark collection, https://portal.uni-freiburg.de/ imteksimulation/downloads/benchmark |
| [38] | T. Penzl, A cyclic low-rank Smith method for large sparse Lyapunov equations, SIAM J. Sci. Comput. 21 (2000), 1401-1418. · Zbl 0958.65052 |
| [39] | T. Penzl, LYAPACK. A MATLAB toolbox for large Lyapunov and Riccati equations, model reduction problems, and linear quadratic optimal control problems, http:// www.tu-chemnitz.de/sfb393/lyapack. |
| [40] | Y. Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., SIAM, 2003. · Zbl 1031.65046 |
| [41] | H. Sadok, CMRH: A new method for solving nonsymmetric linear systems based on the Hessenberg reduction algorithm, Numer. Algorithms 20 (1999), 303-321. · Zbl 0936.65031 |
| [42] | V. Simoncini, A new iterative method for solving large-scale Lyapunov matrix equations, SIAM J. Sci. Comput. 29 (2007), 1268-1288. · Zbl 1146.65038 |
| [43] | R. Smith, Matrix equation XA + BX = C, SIAM J. Appl. Math. 16 (1968), 198-201. · Zbl 0157.22603 |
| [44] | P. Van Dooren, Gramian based model reduction of large-scale dynamical systems, in: Numerical Analysis (Dundee, 1999), Chapman and Hall/CRC, 2000, 231-247. · Zbl 0952.65051 |
| [45] | E. Wachspress, Iterative solution of the Lyapunov matrix equation, Appl. Math. Lett. 107 (1988), 87-90. · Zbl 0631.65037 |
| [46] | J. H. Wilkinson, The Algebraic Eigenvalue Problem, Clarendon Press, Oxford, 1965. · Zbl 0258.65037 |
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.
