A Low-Rank Global Krylov Squared Smith Method for Solving Large-Scale Stein Matrix Equation

Abstract

This paper deals with the numerical solution of the large-scale Stein and discrete-time Lyapunov matrix equations. Based on the global Arnoldi process and the squared Smith iteration, we propose a low-rank global Krylov squared Smith method for solving large-scale Stein and discrete-time Lyapunov matrix equations, and estimate the upper bound of the error and the residual of the approximate solutions for the matrix equations. Moreover, we discuss the restarting of the low-rank global Krylov squared Smith method and provide some numerical experiments to show the efficiency of the proposed method.

Keywords

Stein matrix equation / Lyapunov matrix equation / Squared Smith method / Global Krylov subspace / Restart technique / 65F10 / 65F45

References

[1] Abdaoui I, Elbouyahyaoui L, Heyouni M. An alternative extended block Arnoldi method for solving low-rank Sylvester equations. Comput. Math. Appl.. 2019, 78: 2817-2830

[2] Addam M, Heyouni M, Sadok H. The block Hessenberg process for matrix equations. Electron. Trans. Numer. Anal.. 2017, 46: 460-473

[3] Antoulas AC. Approximation of Large-Scale Dynamical Systems. 2005, Philadelphia, SIAM

[4] Baglama J, Calvetti D, Golub GH, Reichel L. Adaptively preconditioned GMRES algorithms. SIAM J. Sci. Comput.. 1998, 20: 243-269

[5] Bai Z-Z. On Hermitian and skew-Hermitian splitting iteration methods for continuous Sylvester equations. J. Comput. Math.. 2011, 29: 185-198

[6] Bai Z-Z. Motivations and realizations of Krylov subspace methods for large sparse linear systems. J. Comput. Appl. Math.. 2015, 283: 71-78

[7] Bai Z-Z, Guo X-X, Xu S-F. Alternately linearized implicit iteration methods for the minimal nonnegative solutions of nonsymmetric algebraic Riccati equations. Numer. Linear Algebra Appl.. 2006, 13: 655-674

[8] Bai Z-Z, Pan J-Y. Matrix Analysis and Computations. 2021, Philadelphia, SIAM

[9] Bao L, Lin Y-Q, Wei Y-M. A new projection method for solving large Sylvester equations. Appl. Numer. Math.. 2007, 57: 521-532

[10] Barraud AY. A numerical algorithm to solve $A^\text{T}XA-X = Q$. IEEE Trans. Automat. Control. 1977, 22: 883-885

[11] Bartels RH, Stewart GW. Algorithm 432: solution of the matrix equation AX +XB=C. Comm. ACM. 1972, 15: 820-826

[12] Benner P, El Khoury G, Sadkane M. On the squared Smith method for large-scale Stein equations. Numer. Linear Algebra Appl.. 2014, 21: 645-665

[13] Bentbib AH, Jbilou K, Sadek EM. On some extended block Krylov based methods for large scale nonsymmetric Stein matrix equations. Math.. 2017, 5: 21-34

[14] Bertram C, Faßbender H. A quadrature framework for solving Lyapunov and Sylvester equations. Linear Algebra Appl.. 2021, 622: 66-103

[15] Calvetti D, Levenberg N, Reichel L. Iterative methods for $X-AXB=C$. J. Comput. Appl. Math.. 1997, 86: 73-101

[16] Calvetti D, Reichel L. Application of ADI iterative methods to the restoration of noisy images. SIAM J. Matrix Anal. Appl.. 1996, 17: 165-186

[17] Dai H. The Theory of Matrices (in Chinese). 2001, Beijing, Science Press

[18] Datta BN. Numerical Methods for Linear Control Systems. 2003, New York, Academic Press

[19] El Guennouni A, Jbilou K, Riquet AJ. Block Krylov subspace methods for solving large Sylvester equations. Numer. Algorithms. 2002, 29: 75-96

[20] Gao Y-H, Bai Z-Z. On inexact Newton methods based on doubling iteration scheme for nonsymmetric algebraic Riccati equations. Numer. Linear Algebra Appl.. 2011, 18: 325-341

[21] Golub GH, Nash S, Van Loan CF. A Hessenberg-Schur method for the problem AX+XB= C. IEEE Trans. Automat. Control. 1979, 24: 909-913

[22] Golub GH, Van Loan CF. Matrix Computations. 19963Baltimore, Johns Hopkins University Press

[23] Hu D-Y, Reichel L. Krylov subspace methods for the Sylvester equation. Linear Algebra Appl.. 1992, 172: 283-313

[24] Jaimoukha IM, Kasenally EM. Krylov subspace methods for solving large Lyapunov equations. SIAM J. Numer. Anal.. 1994, 31: 227-251

[25] Jbilou K. Low rank approximate solutions to large Sylvester matrix equations. Appl. Math. Comput.. 2006, 177: 365-376

[26] Jbilou K, Messaoudi A. van Dooren P, Bhattacharyya SP, Chan RH, Olshevsky V, Routray A. A computational method for symmetric Stein matrix equations. Numerical Linear Algebra in Signals, Systems and Control. 2011, Dordrecht, Springer: 29531180

[27] Jbilou K, Messaoudi A, Sadok H. Global FOM and GMRES algorithms for matrix equations. Appl. Numer. Math.. 1999, 31: 49-63

[28] Kressner D, Massei S, Robol L. Low-rank updates and a divide-and-conquer method for linear matrix equations. SIAM J. Sci. Comput.. 2019, 41: A848-A876

[29] Lancaster P, Tismenetsky M. The Theory of Matrices. 1985, London, Academic Press

[30] Li T-X, Weng P-C-Y, Chu E-K-W, Lin W-W. Large-scale Stein and Lyapunov equations, Smith method, and applications. Numer. Algorithms. 2013, 63: 727-752

[31] Liao A-P, Bai Z-Z. Least squares symmetric and skew-symmetric solutions of the matrix equation $AXA^\text T+BYB^\text T=C$ with the least norm. Math. Numer. Sinica. 2005, 27: 81-95

[32] Liao A-P, Bai Z-Z, Lei Y. Best approximate solution of matrix equation $AXB + CY D = E$. SIAM J. Matrix Anal. Appl.. 2005, 27: 675-688

[33] Palitta D, Simoncini V. Computationally enhanced projection methods for symmetric Sylvester and Lyapunov matrix equations. J. Comput. Appl. Math.. 2018, 330: 648-659

[34] Penzl T. A cyclic low-rank Smith method for large sparse Lyapunov equations. SIAM J. Sci. Comput.. 2000, 21: 1401-1418

[35] Saad Y, Schultz MH. GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J. Sci. Statis. Comput.. 1986, 7: 856-869

[36] Sadkane M. A low-rank squared Smith method for large-scale discrete-time Lyapunov equations. Linear Algebra Appl.. 2012, 436: 2807-2827

[37] Shafiei SG, Hajarian M. Developing Kaczmarz method for solving Sylvester matrix equations. J. Franklin Inst.. 2022, 359: 8991-9005

[38] Simoncini V. Computational methods for linear matrix equations. SIAM Rev.. 2016, 58: 377-441

[39] Smith RA. Matrix equation $XA+BX=C$. SIAM J. Appl. Math.. 1968, 16: 198-201

[40] Wachspress EL. Iterative solution of the Lyapunov matrix equation. Appl. Math. Lett.. 1988, 1: 87-90

[41] Zhang L, Nodera T. A new adaptive restart for GMRES(m) method. ANZIAM J.. 2004, 46: 409-425

[42] Zhou B, Lamb J, Duan G-R. On Smith-type iterative algorithms for the Stein matrix equation. Appl. Math. Lett.. 2009, 22: 1038-1044

Funding

Innovative Research Group Project of the National Natural Science Foundation of China(No.11571171)

RIGHTS & PERMISSIONS

Shanghai University