10.1007/s40096-023-00516-1

Implicitly restarted global Krylov subspace methods for matrix equations AXB=C

  • Najmeh Azizizadeh1,
  • Azita Tajaddini*1,
  • Amin Rafiei2,
  1. Department of Applied Mathematics, Faculty of Mathematics and Computer, Shahid Bahonar University of Kerman, Kerman, IR
  2. Department of Applied Mathematics, Hakim Sabzevari University, Sabzevar, IR

Published 2023-06-26

How to Cite

Azizizadeh, N., Tajaddini, A., & Rafiei, A. (2023). Implicitly restarted global Krylov subspace methods for matrix equations AXB=C. Mathematical Sciences, 18(4 (December 2024). https://doi.org/10.1007/s40096-023-00516-1
Crossref
Scopus
Google Scholar
Europe PMC

Abstract

Abstract The restarted global Krylov subspace methods are popular to solve matrix equations. Although these methods reduce storage costs, some important information is lost at the time of restart and this slows down the convergence. However, it is possible to keep some crucial information from the previous cycle and then apply them at the restart. To retain this information, it is necessary to update the starting block vector. For this purpose, we introduce the implicitly restarted global Arnoldi process that is based on the implicit double-shift QR iteration. Moreover, we develop the implicitly restarted global FOM and GMRES methods to speed up the convergence. In the mentioned methods, a starting block vector is selected so that the smallest eigenvalues in magnitude are deflated, and the corresponding approximate block Ritz vectors and harmonic Ritz vectors are augmented to the current Krylov subspace, respectively. It is demonstrated that the deflation of the smallest eigenvalues can be particularly imperative for global methods. Finally, the efficiency of these methods are appraised on two academic examples as well as on a case study in surface fitting application.

Keywords

  • Ritz value,
  • Harmonic Ritz value,
  • Implicitly restarted global GMRES

References

  1. Al Daas, H., Grigori, L., Hénon, P., Ricoux, P.: Recycling Krylov subspaces and truncating deflation subspaces for solving sequence of linear systems. PhD thesis, Inria Paris (2018)
  2. Azizizadeh et al. (2019) Weighted and deflated global GMRES algorithms for solving large Sylvester matrix equations 82(1) (pp. 155-181) https://doi.org/10.1007/s11075-018-0597-9
  3. Beik (2011) Extending global full orthogonalization method for solving the matrix equation AXB= F 5(2) (pp. 166-169)
  4. Beik (2011) Note to the global GMRES for solving the matrix equation AXB= F 5(8) (pp. 1165-1169)
  5. Boojhawon and Bhuruth (2004) Restarted simpler GMRES augmented with harmonic Ritz vectors 20(3) (pp. 389-397) https://doi.org/10.1016/j.future.2003.07.004
  6. Bouhamidi and Jbilou (2008) A note on the numerical approximate solutions for generalized Sylvester matrix equations with applications 206(2) (pp. 687-694)
  7. Bouyouli et al. (2006) Convergence properties of some block Krylov subspace methods for multiple linear systems 196(2) (pp. 498-511) https://doi.org/10.1016/j.cam.2005.09.017
  8. Coulaud, O., Giraud, L., Ramet, P., Vasseur, X.: Deflation and augmentation techniques in Krylov subspace methods for the solution of linear systems. arXiv preprint arXiv:1303.5692, (2013)
  9. Cvetković-Iliíc (2006) The reflexive solutions of the matrix equation AX B= C 51(6–7) (pp. 897-902) https://doi.org/10.1016/j.camwa.2005.11.032
  10. Datta, B.N.: Numerical Linear Algebra and Applications, vol. 116. SIAM (2010)
  11. Davis and Hu (2011) The University of Florida sparse matrix collection 38(1) (pp. 1-25)
  12. Elbouyahyaoui, L., Heyouni, M., Tajaddini, A., Saberi-Movahed, F.: On restarted and deflated block FOM and GMRES methods for sequences of shifted linear systems. Numer. Algorithms, 1–43 (2020)
  13. Freund, R.W.: Transpose-free quasi-minimal residual methods for non-Hermitian linear systems. In: Recent Advances in Iterative Methods, pp. 69–94. Springer (1994)
  14. Garcia et al. (2020) Projections, deflation, and multigrid for nonsymmetric matrices 41(1) (pp. 83-105) https://doi.org/10.1137/18M1180268
  15. Gaul et al. (2013) A framework for deflated and augmented Krylov subspace methods 34(2) (pp. 495-518) https://doi.org/10.1137/110820713
  16. Giraud et al. (2010) Flexible GMRES with deflated restarting 32(4) (pp. 1858-1878) https://doi.org/10.1137/080741847
  17. Gutknecht (2014) Deflated and augmented Krylov subspace methods: a framework for deflated BiCG and related solvers 35(4) (pp. 1444-1466) https://doi.org/10.1137/130923087
  18. Huang et al. (2008) An iterative method for the skew-symmetric solution and the optimal approximate solution of the matrix equation AXB= C 212(2) (pp. 231-244) https://doi.org/10.1016/j.cam.2006.12.005
  19. Karimi (2016) The right-left preconditioning technique for the solution of the large matrix equation AXB= C 93(7) (pp. 1226-1239) https://doi.org/10.1080/00207160.2015.1045420
  20. Lancaster, P., Tismenetsky, M.: The Theory of Matrices: with Applications. Elsevier (1985)
  21. Lin et al. (2018) The convergence of least-squares progressive iterative approximation for singular least-squares fitting system 31(6) (pp. 1618-1632) https://doi.org/10.1007/s11424-018-7443-y
  22. Lin et al. (2018) Survey on geometric iterative methods and their applications (pp. 49-51) https://doi.org/10.1016/j.cad.2017.10.002
  23. Lin (2005) Implicitly restarted global FOM and GMRES for nonsymmetric matrix equations and Sylvester equations 167(2) (pp. 1004-1025)
  24. Liu, J., Huang, T.-Z., Lv, X.-G., Xu, H., Zhao, X.-L.: Global quasi-minimal residual method for image restoration. Math. Prob. Eng. 2015 (2015)
  25. Liu et al. (2018) Progressive iterative approximation for regularized least square bivariate B-spline surface fitting (pp. 175-187) https://doi.org/10.1016/j.cam.2017.06.013
  26. Liu et al. (2020) Stationary splitting iterative methods for the matrix equation AXB= C (pp. 125-195)
  27. Meng et al. (2014) A deflated block flexible GMRES-DR method for linear systems with multiple right-hand sides (pp. 478-496)
  28. Mohseni Moghadam et al. (2015) Convergence analysis of the Global FOM and GMRES methods for solving matrix equations AXB= C with SPD coefficients 44(4) (pp. 981-1001)
  29. Morgan (1995) A restarted GMRES method augmented with eigenvectors 16(4) (pp. 1154-1171) https://doi.org/10.1137/S0895479893253975
  30. Morgan (2000) Implicitly restarted GMRES and Arnoldi methods for nonsymmetric systems of equations 21(4) (pp. 1112-1135) https://doi.org/10.1137/S0895479897321362
  31. Morgan (2002) GMRES with deflated restarting 24(1) (pp. 20-37) https://doi.org/10.1137/S1064827599364659
  32. Morgan and Zeng (1998) Harmonic projection methods for large non-symmetric eigenvalue problems 5(1) (pp. 33-55) https://doi.org/10.1002/(SICI)1099-1506(199801/02)5:1<33::AID-NLA125>3.0.CO;2-1
  33. Peng et al. (2005) An iteration method for the symmetric solutions and the optimal approximation solution of the matrix equation AXB= C 160(3) (pp. 763-777)
  34. Peng (2010) New matrix iterative methods for constraint solutions of the matrix equation AXB= C 235(3) (pp. 726-735) https://doi.org/10.1016/j.cam.2010.07.001
  35. Peng, Z.-Y.: New matrix iterative methods for constraint solutions of the matrix equation AXB= C. J. Comput. Appl. Math. 235(3), 726–735 (2010)
  36. Regalia and Sanjit (1989) Kronecker products, unitary matrices and signal processing applications 31(4) (pp. 586-613) https://doi.org/10.1137/1031127
  37. Saad, Y.: Iterative Methods for Sparse Linear Systems. SIAM (2003)
  38. Shahzadeh Fazeli et al. (2015) A key to choose subspace size in implicitly restarted Arnoldi method 70(2) (pp. 407-426) https://doi.org/10.1007/s11075-014-9954-5
  39. Sorensen (1992) Implicit application of polynomial filters in ak-step Arnoldi method 13(1) (pp. 357-385) https://doi.org/10.1137/0613025
  40. Sun et al. (2019) Flexible and deflated variants of the block shifted GMRES method (pp. 168-183) https://doi.org/10.1016/j.cam.2018.05.053
  41. Sun et al. (2018) A block GMRES method with deflated restarting for solving linear systems with multiple shifts and multiple right-hand sides 25(5) https://doi.org/10.1002/nla.2148
  42. Tajaddini et al. (2021) Two new variants of the simpler block GMRES method with vector deflation and eigenvalue deflation for multiple linear systems 86(1) (pp. 1-33) https://doi.org/10.1007/s10915-020-01376-w
  43. Zak and Toutounian (2013) Nested splitting conjugate gradient method for matrix equation AXB= C and preconditioning 66(3) (pp. 269-278) https://doi.org/10.1016/j.camwa.2013.05.004
  44. Zhong et al. (2015) A flexible and adaptive simpler block GMRES with deflated restarting for linear systems with multiple right-hand sides (pp. 139-156) https://doi.org/10.1016/j.cam.2014.12.040