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

doi:10.1007/s42967-023-00364-9

Communications on Applied Mathematics and Computation ›› 2025, Vol. 7 ›› Issue (2): 562-588.doi: 10.1007/s42967-023-00364-9

• ORIGINAL PAPERS • 上一篇下一篇

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

Song Nie¹, Hua Dai¹

School of Mathematics, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, Jiangsu, China

收稿日期:2023-10-08 修回日期:2023-12-18 接受日期:2023-12-19 出版日期:2025-06-20 发布日期:2025-04-21
通讯作者: Hua Dai,hdai@nuaa.edu.cn;Song Nie,niesong1995@nuaa.edu.cn E-mail:hdai@nuaa.edu.cn;niesong1995@nuaa.edu.cn
基金资助:
The work is supported by the National Natural Science Foundation of China under grant No.11571171. The authors are very grateful to the anonymous referees for their useful comments and suggestions which greatly improved the representation of this paper.

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

Song Nie¹, Hua Dai¹

School of Mathematics, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, Jiangsu, China

Received:2023-10-08 Revised:2023-12-18 Accepted:2023-12-19 Online:2025-06-20 Published:2025-04-21
Supported by:
The work is supported by the National Natural Science Foundation of China under grant No.11571171. The authors are very grateful to the anonymous referees for their useful comments and suggestions which greatly improved the representation of this paper.

摘要/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.

关键词: Stein matrix equation, Lyapunov matrix equation, Squared Smith method, Global Krylov subspace, Restart technique

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

中图分类号:

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.

参考文献

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.

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

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 13

编辑推荐

Metrics

本文评价