Theory of Krylov subspace methods based on the Arnoldi process with inexact inner products

Meng Su; Chun Wen; Zhao-Li Shen; Stefano Serra-Capizzano; Meng Su; Chun Wen; Zhao-Li Shen; Stefano Serra-Capizzano

doi:10.3934/nhm.2025002

Networks and Heterogeneous Media

2025, Volume 20, Issue 1: 15-34. doi: 10.3934/nhm.2025002

Previous Article Next Article

Research article Special Issues

Theory of Krylov subspace methods based on the Arnoldi process with inexact inner products

1.
School of Mathematical Sciences, University of Electronic Science and Technology of China, Chengdu, Sichuan 610054, China
2.
College of Science, Sichuan Agricultural University, Ya'an, Sichuan 625000, China
3.
Department of Science and High Technology, University of Insubria, Como Campus 22100, Italy

Received: 21 October 2024 Revised: 20 December 2024 Accepted: 27 December 2024 Published: 06 January 2025

Several Krylov subspace methods are based on the Arnoldi process, such as the full orthogonalization method (FOM), GMRES, and in general all the Arnoldi-type methods. In fact, the Arnoldi process is an algorithm for building an orthogonal basis of the Krylov subspace. Once the inner products are performed inexactly, which cannot be avoided due to round-off errors, the orthogonality of Arnoldi vectors is lost. In this paper, we presented a new analysis framework to show how the inexact inner products influence the Krylov subspace methods that are based on the Arnoldi process. A new metric was developed to quantify the inexactness of the Arnoldi process with inexact inner products. In addition, the proposed metric can be used to approximately estimate the loss of orthogonality in the practical use of the Arnoldi process. The discrepancy in residual gaps between Krylov subspace methods employing inexact inner products and their corresponding exact counterparts was discussed. Numerical experiments on several examples were reported to illustrate our theoretical findings and final observations were presented.
- Arnoldi process,
- Krylov subspace methods,
- inexact inner products,
- residual gaps
Citation: Meng Su, Chun Wen, Zhao-Li Shen, Stefano Serra-Capizzano. Theory of Krylov subspace methods based on the Arnoldi process with inexact inner products[J]. Networks and Heterogeneous Media, 2025, 20(1): 15-34. doi: 10.3934/nhm.2025002

Related Papers:

Abstract

Several Krylov subspace methods are based on the Arnoldi process, such as the full orthogonalization method (FOM), GMRES, and in general all the Arnoldi-type methods. In fact, the Arnoldi process is an algorithm for building an orthogonal basis of the Krylov subspace. Once the inner products are performed inexactly, which cannot be avoided due to round-off errors, the orthogonality of Arnoldi vectors is lost. In this paper, we presented a new analysis framework to show how the inexact inner products influence the Krylov subspace methods that are based on the Arnoldi process. A new metric was developed to quantify the inexactness of the Arnoldi process with inexact inner products. In addition, the proposed metric can be used to approximately estimate the loss of orthogonality in the practical use of the Arnoldi process. The discrepancy in residual gaps between Krylov subspace methods employing inexact inner products and their corresponding exact counterparts was discussed. Numerical experiments on several examples were reported to illustrate our theoretical findings and final observations were presented.

References

[1]	Z. Bai, J. Demmel, J. Dongarra, A. Ruhe, H. van der Vorst, Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide, Society for Industrial and Applied Mathematics, Philadelphia, USA, 2000.
[2]	A. Greenbaum, Iterative Methods for Solving Linear Systems, Society for Industrial and Applied Mathematics, Philadelphia, 1997.
[3]	Y. Saad, Numerical Methods for Large Eigenvalue Problems, Halstead Press, New York, 1992.
[4]	Y. Saad, Iterative Methods for Sparse Linear Systems, PWS Publishing, Boston, MA, USA, 1996.
[5]	A. Bouras, V. Frayssé, A relaxation strategy for inexact matrix-vector products for Krylov methods, Technical Report 15, CERFACS, Toulouse, France, 2000.
[6]	A. Bouras, V. Frayssé, Inexact matrix-vector products in Krylov methods for solving linear systems: A relaxation strategy, SIAM J. Matrix Anal. Appl., 26 (2005), 660–678. https://doi.org/10.1137/s0895479801384743 doi: 10.1137/s0895479801384743
[7]	J. van den Eshof, G. L. G. Sleijpen, Inexact Krylov subspace methods for linear systems, SIAM J. Matrix Anal. Appl., 26 (2004), 125–153. https://doi.org/10.1137/S0895479802403459 doi: 10.1137/S0895479802403459
[8]	V. Simoncini, D. B. Szyld, Theory of inexact Krylov subspace methods and applications to scientific computing, SIAM J. Sci. Comput., 25 (2003), 454–477. https://doi.org/10.1137/s1064827502406415 doi: 10.1137/s1064827502406415
[9]	G. L. G. Sleijpen, J. van den Eshof, M. B. van Gijzen, Restarted GMRES with inexact matrix–vector products, in Numerical Analysis and Its Applications: Third International Conference, NAA 2004, Springer-Verlag Berlin Heidelberg, (2005), 494–502. https://doi.org/10.1007/978-3-540-31852-1_60
[10]	S. Gratton, E. Simon, D. Titley-Peloquin, P. L. Toint, A note on inexact inner products in GMRES, SIAM J. Matrix Anal. Appl., 43 (2022), 1406–1422. https://doi.org/10.1137/20m1320018 doi: 10.1137/20m1320018
[11]	L. Giraud, S. Gratton, J. Langou, Convergence in backward error of relaxed GMRES, SIAM J. Sci. Comput., 29 (2007), 710–728. https://doi.org/10.1137/040608416 doi: 10.1137/040608416
[12]	V. Simoncini, D. B. Szyld, Recent computational developments in Krylov subspace methods for linear systems, Numer. Linear Algebra Appl., 14 (2007), 1–59. https://doi.org/10.1002/nla.499 doi: 10.1002/nla.499
[13]	A. Bouras, V. Frayssé, L. Giraud, A relaxation strategy for inner-outer linear solvers in domain decomposition methods, Technical Report 17, CERFACS, Toulouse, France, 2000.
[14]	P. Kürschner, M. A. Freitag, Inexact methods for the low rank solution to large scale Lyapunov equations, BIT Numer. Math., 60 (2020), 1221–1259. https://doi.org/10.1007/s10543-020-00813-4 doi: 10.1007/s10543-020-00813-4
[15]	S. J. Leon, A. Björck, W. Gander, Gram-Schmidt orthogonalization: 100 years and more, Numer. Linear Algebra Appl., 20 (2013), 175–188. https://doi.org/10.1002/nla.1839 doi: 10.1002/nla.1839
[16]	A. Björck, Solving linear least squares problems by Gram-Schmidt orthogonalization, BIT Numer. Math., 7 (1967), 1–21. https://doi.org/10.1007/bf01934122 doi: 10.1007/bf01934122
[17]	A. Björck, C. C. Paige, Loss and recapture of orthogonality in the modified Gram–Schmidt algorithm, SIAM J. Matrix Anal. Appl., 13 (1992), 176–190. https://doi.org/10.1137/0613015 doi: 10.1137/0613015
[18]	J. Drko$ \breve{\rm s}$ová, A. Greenbaum, M. Rozlo$ \breve{\rm z}$ník, Z. Strako$ \breve{\rm s}$, Numerical stability of GMRES, BIT Numer. Math., 35 (1995), 309–330. https://doi.org/10.1007/bf01732607
[19]	A. Greenbaum, M. Rozlo$ \breve{\rm z}$ník, Z. Strako$ \breve{\rm s}$, Numerical behaviour of the modified Gram–Schmidt GMRES implementation, BIT Numer. Math, 37 (1997), 706–719. https://doi.org/10.1007/bf02510248 doi: 10.1007/bf02510248
[20]	C. C. Paige, M. Rozlo$ \breve{\rm z}$ník, Z. Strako$ \breve{\rm s}$, Modified Gram–Schmidt (MGS), least squares, and backward stability of MGS-GMRES, SIAM J. Matrix Anal. Appl., 28 (2006), 264–284. https://doi.org/10.1137/050630416 doi: 10.1137/050630416
[21]	R. A. Horn, C. R. Johnson, Matrix Analysis, Cambridge University Press, Cambridge, UK, 2013.
[22]	G. H. Golub, C. F. Van Loan, Matrix Computations, Johns Hopkins University Press, Baltimore, USA, 2013.
[23]	A. Stathopoulos, K. Wu, A block orthogonalization procedure with constant synchronization requirements, SIAM J. Sci. Comput., 23 (2002), 2165–2182. https://doi.org/10.1137/s1064827500370883 doi: 10.1137/s1064827500370883
[24]	R. A. Horn, C. R. Johnson, Topics in Matrix Analysis, Cambridge University Press, Cambridge, UK, 1994.
[25]	G. W. Stewart, Introduction to Matrix Computations, Academic Press, New York-London, 1973.
[26]	Y. Saad, M. H. Schultz, GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 7 (1986), 856–869. https://doi.org/10.1137/0907058 doi: 10.1137/0907058
[27]	C. L. Lawson, R. J. Hanson, Solving Least Squares Problems, Society for Industrial and Applied Mathematics, Philadelphia, USA, 1995.
[28]	G. H. Golub, C. Greif, An Arnoldi-type algorithm for computing page rank, BIT Numer. Math., 46 (2006), 759–771. https://doi.org/10.1007/s10543-006-0091-y doi: 10.1007/s10543-006-0091-y
[29]	Z. Jia, Refined iterative algorithms based on Arnoldi's process for large unsymmetric eigenproblems, Linear Algebra Appl., 259 (1997), 1–23. https://doi.org/10.1016/S0024-3795(96)00238-8 doi: 10.1016/S0024-3795(96)00238-8
[30]	G. Barbarino, C. Garoni, S. Serra-Capizzano, Block generalized locally Toeplitz sequences: Theory and applications in the multidimensional case, Electron. Trans. Numer. Anal., 53 (2020), 113–216. https://doi.org/10.1553/etna_vol53s113 doi: 10.1553/etna_vol53s113
[31]	S. Serra-Capizzano, P. Tilli, Extreme singular values and eigenvalues of non-Hermitian block Toeplitz matrices, J. Comput. Appl. Math., 108 (1999), 113–130. https://doi.org/10.1016/s0377-0427(99)00104-1 doi: 10.1016/s0377-0427(99)00104-1
[32]	R. Bhatia, Matrix Analysis, Graduate Texts in Mathematics, Springer-Verlag, New York, USA, 1997.
[33]	T. A. Davis, Y. Hu, The University of Florida sparse matrix collection, ACM Trans. Math. Software, 38 (2011), 1–25. https://doi.org/10.1145/2049662.20496 doi: 10.1145/2049662.20496
[34]	L. Page, S. Brin, R. Motwani, T. Winograd, The PageRank citation ranking: Bringing order to the web, Technical Report, Stanford University, USA, 1998.
[35]	G. Del Corso, A. Gullí, F. Romani, Comparison of Krylov subspace methods on the PageRank problem, J. Comput. Appl. Math., 210-1/2 (2007), 159–166. https://doi.org/10.1016/j.cam.2006.10.080 doi: 10.1016/j.cam.2006.10.080
[36]	S. Serra-Capizzano, Jordan canonical form of the Google matrix: A potential contribution to the PageRank computation, SIAM J. Matrix Anal. Appl., 27 (2005), 305–312. https://doi.org/10.1137/s0895479804441407 doi: 10.1137/s0895479804441407
[37]	R. A. Horn, S. Serra-Capizzano, A general setting for the parametric Google matrix, Internet Math., 3 (2006), 385–411. https://doi.org/10.1080/15427951.2006.10129131 doi: 10.1080/15427951.2006.10129131

Reader Comments

Your name:*

Email:*
© 2025 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)