A GPU / CPU faster block Arnoldi method for solving large-scale Lyapunov equation

Document Type : Research Article

Author

ENSA Oujda, Equipe MSN, Lab. LM2N, Université Mohammed Premier, Morocco

Abstract

Krylov methods have proven effective in solving large-scale matrix equations with sparse coefficients, in particular through the use of the extended Arnoldi process, which involves the inverse of the matrix coefficients in the projection subspace. This approach has significantly reduced the time and number of iterations needed to find a suitable solution. In this paper, we are interested on solving the low-rank Lyapunov equation whether in the continuous or discrete case. We propose to enhance the convergence time by modifying the Block Arnoldi process so that the Krylov projection subspace contains additional blocks from the inverse of the square coefficient of this equation. Our intention is to benefit from these additional informations, similar to the extended Arnoldi version, without incorporating them at each iteration, thus preventing any impact on the convergence speed. To confirm the effectiveness of the proposed method, some numerical results obtained using CPU and GPU implementations are provided.

Keywords

Main Subjects

References

[1] I. Abdaoui, L. Elbouyahyaoui, M. Heyouni, An alternative extended block Arnoldi method for solving low-rank Sylvester equations, Comput. Math. Appl. 78 (2019) 2817--2830.
[2] I. Abdaoui, An improved extended block Arnoldi method for solving low-rank Lyapunov equation, J. Math. Model. 12 (2024) 85--98.
[3] A.C. Antoulas, Approximation of large-scale dynamical systems, SIAM (2005).
[4] M. Bagheri, F. Kyanfar, A. Salemi, A. Tajaddini, A modified block Hessenberg method for low-rank tensor Sylvester equation, J. Comput. Appl. Math. 456 (2025) 116209.
[5] R.H. Bartels, G.W. Stewart, Solution of the matrix equation AX+XB=C, Commun. ACM. 15 (1972) 820--826.
[6] P. Benner, E. Quintana-Ortí, Solving stable generalized Lyapunov equations with the matrix sign function, Numer. Algorithms. 20 (1999) 75--100.
[7] A. Bouhamidi, M. Hached, M. Heyouni, K. Jbilou, A preconditioned block Arnoldi method for large Sylvester matrix equations, SIAM J. Numer. Anal. 20 (2013) 208--219.
[8] A.A. Casulli, Tensorized block rational Krylov methods for tensor Sylvester equations, IMA J. Numer. Anal. (2025) (in press).
[9] T. Damm, Direct methods and ADI-preconditioned Krylov subspace methods for generalized Lyapunov equations, Numer. Linear Algebra Appl. 15 (2008) 853--871.
[10] B. Datta, Krylov subspace methods for large-scale matrix problems in control, Future Gener. Comput. Syst. 19 (2003) 1253--1263.
[11] T.A. Davis, Y. Hu, The University of Florida sparse matrix collection, ACM Trans. Math. Softw. 38 (2011) 1--25.
[12] V. Druskin, L. Knizhnerman, Extended Krylov subspaces: approximation of the matrix square root and related functions, SIAM J. Matrix Anal. Appl. 19 (1998) 755--771.
[13] V. Druskin, L. Knizhnerman, V. Simoncini, Analysis of the rational Krylov subspace and ADI methods for solving the Lyapunov equation, SIAM J. Numer. Anal. 49 (2011) 1875--1898.
[14] N. Ellner, E. Wachspress, Alternating direction implicit iteration for systems with complex spectra, SIAM J. Numer. Anal. 28 (1991) 859--870.
[15] A. Eppler, M. Bollhöfer, An alternative way of solving large Lyapunov equations, PAMM. 10 (2010) 547--548.
[16] Z. Gajic, M. Qureshi, Lyapunov matrix equation in system stability and control, Courier Corporation (2008).
[17] G.H. Golub, S. Nash, C.F. Van Loan, A Hessenberg--Schur method for the problem AX+XB=C, IEEE Trans. Automat. Control. 24 (1979) 909--913.
[18] G.H. Golub, C.F. Van Loan, Matrix Computations, Johns Hopkins University Press (2013).
[19] L. Grasedyck, Existence of a low rank or H-matrix approximant to the solution of a Sylvester equation, Numer. Linear Algebra Appl. 11 (2004) 371--389.
[20] M. Heyouni, K. Jbilou, An extended block Arnoldi algorithm for large-scale solutions of the continuous-time algebraic Riccati equation, Electron. Trans. Numer. Anal. 33 (2009) 53--62.
[21] M. Heyouni, Extended Arnoldi methods for large low-rank Sylvester matrix equations, Appl. Numer. Math. 60 (2010) 1171--1182.
[22] T. Hinamoto, 2-D Lyapunov equation and filter design based on the Fornasini--Marchesini second model, IEEE Trans. Circuits Syst. I. 40 (1993) 102--110.
[23] A. Hodel, K. Poolla, Parallel solution of large Lyapunov equations, SIAM J. Matrix Anal. Appl. 13 (1992) 1189--1203.
[24] L. Sadek, H. Talibi Alaoui, The extended block Arnoldi method for solving generalized differential Sylvester equations, J. Math. Model. 8 (2020) 189--206.
[25] A. Tajaddini, Extended block Hessenberg method for large-scale Sylvester differential matrix equations, J. Mahani Math. Res. 13 (2024) 383--409.
Journal of Mathematical Modeling
Volume 14, Issue 3
August 2026
Pages 1107-1124

Files

Share

How to cite

Statistics