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

doi:10.1007/s42967-023-00364-9

Abstract

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 largescale 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.

Key words: Stein matrix equation, Lyapunov matrix equation, Squared Smith method, Global Krylov subspace, Restart technique

CLC Number:

65F10
65F45

Song Nie, Hua Dai. A Low-Rank Global Krylov Squared Smith Method for Solving Large-Scale Stein Matrix Equation[J]. Communications on Applied Mathematics and Computation, 2025, 7(2): 562-588.

TrendMD

References

1. Abdaoui, I., Elbouyahyaoui, L., Heyouni, M.: An alternative extended block Arnoldi method for solving lowrank Sylvester equations. Comput. Math. Appl. 78, 2817–2830 (2019)
2. Addam, M., Heyouni, M., Sadok, H.: The block Hessenberg process for matrix equations. Electron. Trans. Numer. Anal. 46, 460–473 (2017)
3. Antoulas, A.C.: Approximation of Large-Scale Dynamical Systems. SIAM, Philadelphia (2005)
4. Baglama, J., Calvetti, D., Golub, G.H., Reichel, L.: Adaptively preconditioned GMRES algorithms. SIAM J. Sci. Comput. 20, 243–269 (1998)
5. Bai, Z.-Z.: On Hermitian and skew-Hermitian splitting iteration methods for continuous Sylvester equations. J. Comput. Math. 29, 185–198 (2011)
6. Bai, Z.-Z.: Motivations and realizations of Krylov subspace methods for large sparse linear systems. J. Comput. Appl. Math. 283, 71–78 (2015)
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. 13, 655–674 (2006)
8. Bai, Z.-Z., Pan, J.-Y.: Matrix Analysis and Computations. SIAM, Philadelphia (2021)
9. Bao, L., Lin, Y.-Q., Wei, Y.-M.: A new projection method for solving large Sylvester equations. Appl. Numer. Math. 57, 521–532 (2007)
10. Barraud, A.Y.: A numerical algorithm to solve A^TXA - X = Q. IEEE Trans. Automat. Control 22, 883– 885 (1977)
11. Bartels, R.H., Stewart, G.W.: Algorithm 432: solution of the matrix equation AX +XB=C. Comm. ACM 15, 820–826 (1972)
12. Benner, P., El Khoury, G., Sadkane, M.: On the squared Smith method for large-scale Stein equations. Numer. Linear Algebra Appl. 21, 645–665 (2014)
13. Bentbib, A.H., Jbilou, K., Sadek, E.M.: On some extended block Krylov based methods for large scale nonsymmetric Stein matrix equations. Math. 5, 21–34 (2017)
14. Bertram, C., Faßbender, H.: A quadrature framework for solving Lyapunov and Sylvester equations. Linear Algebra Appl. 622, 66–103 (2021)
15. Calvetti, D., Levenberg, N., Reichel, L.: Iterative methods for X - AXB = C. J. Comput. Appl. Math. 86, 73–101 (1997)
16. Calvetti, D., Reichel, L.: Application of ADI iterative methods to the restoration of noisy images. SIAM J. Matrix Anal. Appl. 17, 165–186 (1996)
17. Dai, H.: The Theory of Matrices (in Chinese). Science Press, Beijing (2001)
18. Datta, B.N.: Numerical Methods for Linear Control Systems. Academic Press, New York (2003)
19. El Guennouni, A., Jbilou, K., Riquet, A.J.: Block Krylov subspace methods for solving large Sylvester equations. Numer. Algorithms 29, 75–96 (2002)
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. 18, 325–341 (2011)
21. Golub, G.H., Nash, S., Van Loan, C.F.: A Hessenberg-Schur method for the problem AX+XB= C. IEEE Trans. Automat. Control 24, 909–913 (1979)
22. Golub, G.H., Van Loan, C.F.: Matrix Computations, 3rd edn. Johns Hopkins University Press, Baltimore (1996)
23. Hu, D.-Y., Reichel, L.: Krylov subspace methods for the Sylvester equation. Linear Algebra Appl. 172, 283–313 (1992)
24. Jaimoukha, I.M., Kasenally, E.M.: Krylov subspace methods for solving large Lyapunov equations. SIAM J. Numer. Anal. 31, 227–251 (1994)
25. Jbilou, K.: Low rank approximate solutions to large Sylvester matrix equations. Appl. Math. Comput. 177, 365–376 (2006)
26. Jbilou, K., Messaoudi, A.: A computational method for symmetric Stein matrix equations. In: van Dooren, P., Bhattacharyya, S.P., Chan, R.H., Olshevsky, V., Routray, A. (eds.) Numerical Linear Algebra in Signals, Systems and Control. Lecture Notes in Electrical Engineering, vol. 80, pp. 295–311. Springer, Dordrecht (2011)
27. Jbilou, K., Messaoudi, A., Sadok, H.: Global FOM and GMRES algorithms for matrix equations. Appl. Numer. Math. 31, 49–63 (1999)
28. Kressner, D., Massei, S., Robol, L.: Low-rank updates and a divide-and-conquer method for linear matrix equations. SIAM J. Sci. Comput. 41, A848–A876 (2019)
29. Lancaster, P., Tismenetsky, M.: The Theory of Matrices. Academic Press, London (1985)
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 63, 727–752 (2013)
31. Liao, A.-P., Bai, Z.-Z.: Least squares symmetric and skew-symmetric solutions of the matrix equation AXAT + BYBT = C with the least norm. Math. Numer. Sinica 27, 81–95 (2005)
32. Liao, A.-P., Bai, Z.-Z., Lei, Y.: Best approximate solution of matrix equation AXB + CYD = E. SIAM J. Matrix Anal. Appl. 27, 675–688 (2005)
33. Palitta, D., Simoncini, V.: Computationally enhanced projection methods for symmetric Sylvester and Lyapunov matrix equations. J. Comput. Appl. Math. 330, 648–659 (2018)
34. Penzl, T.: A cyclic low-rank Smith method for large sparse Lyapunov equations. SIAM J. Sci. Comput. 21, 1401–1418 (2000)
35. Saad, Y., Schultz, M.H.: GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J. Sci. Statis. Comput. 7, 856–869 (1986)
36. Sadkane, M.: A low-rank squared Smith method for large-scale discrete-time Lyapunov equations. Linear Algebra Appl. 436, 2807–2827 (2012)
37. Shafiei, S.G., Hajarian, M.: Developing Kaczmarz method for solving Sylvester matrix equations. J. Franklin Inst. 359, 8991–9005 (2022)
38. Simoncini, V.: Computational methods for linear matrix equations. SIAM Rev. 58, 377–441 (2016)
39. Smith, R.A.: Matrix equation XA + BX = C. SIAM J. Appl. Math. 16, 198–201 (1968)
40. Wachspress, E.L.: Iterative solution of the Lyapunov matrix equation. Appl. Math. Lett. 1, 87–90 (1988)
41. Zhang, L., Nodera, T.: A new adaptive restart for GMRES(m) method. ANZIAM J. 46, 409–425 (2004)
42. Zhou, B., Lamb, J., Duan, G.-R.: On Smith-type iterative algorithms for the Stein matrix equation. Appl. Math. Lett. 22, 1038–1044 (2009)

[1]	Gui-Lin Yan, Yu-Jiang Wu, Bo Deng. Improvement of Convergence of One- and Two-Step MSM Iteration Methods for Nondifferentiable Nonlinear Complementarity Problems [J]. Communications on Applied Mathematics and Computation, 2025, 7(2): 733-758.
[2]	M. Pakmanesh, Hamidreza Afshin. T_M-Eigenvalues of Odd-Order Tensors [J]. Communications on Applied Mathematics and Computation, 2022, 4(4): 1258-1279.
[3]	Guangbin Wang, Fuping Tan. Modulus-Based Multisplitting Iteration Method for a Class of Weakly Nonlinear Complementarity Problem [J]. Communications on Applied Mathematics and Computation, 2021, 3(3): 419-428.
[4]	Yun Miao, Liqun Qi, Yimin Wei. T-Jordan Canonical Form and T-Drazin Inverse Based on the T-Product [J]. Communications on Applied Mathematics and Computation, 2021, 3(2): 201-220.
[5]	Wei Wei, Hui Zhang, Xi Yang, Xiaoping Chen. Randomized Generalized Singular Value Decomposition [J]. Communications on Applied Mathematics and Computation, 2021, 3(1): 137-156.
[6]	Jun-Feng Yin, Yi-Shu Du. A Class of Preconditioners Based on Positive-Definite Operator Splitting Iteration Methods for Variable-Coefficient Space-Fractional Diffusion Equations [J]. Communications on Applied Mathematics and Computation, 2021, 3(1): 157-176.
[7]	Ju, Li Zhang. On the Preconditioning Properties of RHSS Preconditioner for Saddle-Point Linear Systems [J]. Communications on Applied Mathematics and Computation, 2021, 3(1): 177-187.
[8]	Fang Chen, Cun, Qiang Miao, Galina V. Muratova. On Convergence of MRQI and IMRQI Methods for Hermitian Eigenvalue Problems [J]. Communications on Applied Mathematics and Computation, 2021, 3(1): 189-197.
[9]	Bangti Jin, Zhi Zhou. Multigrid Methods for Time-Fractional Evolution Equations: A Numerical Study [J]. Communications on Applied Mathematics and Computation, 2020, 2(2): 163-177.
[10]	Qiaohua Liu, Lei Yao, Aijing Liu. A Note on the Adaptive Simpler Block GMRES Method [J]. Communications on Applied Mathematics and Computation, 2019, 1(3): 435-447.
[11]	Wen-Ting Wu. On Minimization of Upper Bound for the Convergence Rate of the QHSS Iteration Method [J]. Communications on Applied Mathematics and Computation, 2019, 1(2): 263-282.
[12]	Kang-Ya Lu, Shu-Jiao Li. Semi-regularized Hermitian and Skew-Hermitian Splitting Preconditioning for Saddle-Point Linear Systems [J]. Communications on Applied Mathematics and Computation, 2023, 5(4): 1422-1445.
[13]	Bo Wu, Xingbao Gao. Two-Parameter Block Triangular Splitting Preconditioner for Block Two-by-Two Linear Systems [J]. Communications on Applied Mathematics and Computation, 2023, 5(4): 1601-1615.