Abstract
In this paper, we present a comprehensive framework for studying Krylov subspace methods used to solve the linear system \(Ax=f\). These methods aim to achieve convergence within a specified number of iterations, denoted by m, given a particular initial estimate vector \(x_0\) and its corresponding residual \(r_0=f-Ax_0\). Our analysis focuses on the minimal polynomial \({\varPhi }_m\) of degree m of A for the vector \(r_0\). We establish that these methods encompass Petrov-Galerkin methods and minimal seminorm methods as special cases. Additionally, we demonstrate that minimal seminorm methods satisfy implicit Petrov-Galerkin conditions. We provide a general formulation for the iterates based on generalized inverses. The choice of a specific left inverse and the method of constructing the Krylov basis are crucial distinguishing factors among different Krylov subspace methods. We describe and analyze the mathematical properties of these methods, emphasizing their dependency on two matrices. Notably, we prove that CMRH and QMR, as specific instances, also satisfy implicit Petrov-Galerkin orthogonality conditions. Furthermore, we explore techniques to improve the convergence behavior of these methods by carefully selecting vectors in their implementations. Through our investigation, we aim to deepen the understanding of Krylov subspace methods, provide insights into their convergence properties, and identify potential enhancements. We also consider some Krylov subspace methods, which are of product-type methods. In this case, the kth residual \(r_k\) associated with the approximation \(x_k\) of the exact solution is given by \(r_k={\varPsi }_k(A){\varPhi }_k(A)r_0\), and \({\varPsi }_k\) is a polynomial of fixed or variable degree. We will examine particular choices of \({\varPsi }_k\) involving local convergence, smoothing, fixed memory, and cost for each iteration. We will also give an enhancement of some product-type methods such as CGS. To illustrate the performance of the derived algorithms, we provide some numerical examples.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Data availability
Data sharing not applicable to this article as no data sets were generated or analyzed during the current study. We just improved existing programs.
References
Ben-Israel, A., Greville, T.N.E.: Generalized inverse, theory and application, 2nd edn. Canadian Mathematical Society, Ottawa (2003)
Bouyghf, F.: An enhancement of the convergence of the BiCGStab method for solving linear systems with single or multiple right-hand sides, submitted to Computational and mathematical methods
Bouyghf, F., Messaoudi, A., Sadok, H.: An enhancement of the convergence of IDR method. Electron. Trans. Numer. Anal. 58, 470–485 (2023)
Brezinski, C., Redivo-Zaglia, M., Sadok, H.: Avoiding breakdown and near breakdown in Lanczos-type algorithms. Numer. Algorithms 1, 199–206 (1991)
Brezinski, C., Redivo-Zaglia, M., Sadok, H.: The matrix and polynomial approaches to Lanczos-type algorithms. Numer. Math. 45, 361–376 (1992)
Brezinski, C., Redivo-Zaglia, M., Sadok, H.: The matrix and polynomial approaches to Lanczos-type algorithms. J. Comput. Appl. Math. 123, 241–260 (2000)
Fletcher, R.: Conjugate gradient methods for indefinite systems. In: Watson, G.A. (ed.) Numerical analysis, Dundee 1975. Lecture Notes in Mathematics, vol. 506. Springer, Berlin (1976)
Freund, R.W., Nachtigal, N.M.: QMR: a quasi minimal residual method for non-Hermitian linear systems. Numer. Math. 60, 315–339 (1991)
Freund, R.W., Gutknecht, M.H., Nachtigal, N.M.: An implementation of the look-ahead Lanczos algorithm for non-Hermitian matrices. SIAM J. Sci. Comput. 14, 137–158 (1993)
Greville, T.N.E.: Some applications of the pseudoinverse of a matrix. SIAM Rev. 2, 15–22 (1960)
Hestenes, M.R., Stiefel, E.: Methods of conjugate gradients for solving linear systems. J. Res. Natl. Bur. Stand. 49, 409–436 (1952)
Heyouni, M., Sadok, H.: On a variable smoothing procedure for Krylov subspaces methods. Linear Algebra Appl. 268, 131–149 (1998)
Householder, A.S., Bauer, F.L.: On certain methods for expanding the characteristic polynomial. Numer. Math. 1, 29–37 (1959)
Joubert, W.: Lanczos methods for the solution of nonsymmetric systems of linear equations. SIAM Matrix Anal. Appl. 13, 926–943 (1992)
Lanczos, C.: Solution of systems of linear equations by minimized iterations. J. Res. Nat. Bur. stand. 49, 33–53 (1952)
Liesen, J., Strakos, Z.: Krylov subspace methods principles and analysis, 1st edn. Oxford University Press, Oxford (2013)
Meurant, G., Tabbens, J.D.: Krylov methods for non-symmetric linear systems: from theory to computations. In: Springer Series in Computational Mathematics, vol. 57 (2020)
Nachtigal, N.M.: A look-ahead variant of the Lanczos algorithm and its application to the quasi minimal residual method for nonhermitian linear systems. Ph.D. thesis, Massachusetts Institute of Technology (1991)
Parlett, B.N.: Reduction to tridiagonal form and minimal realizations. SIAM J. Matrix Anal. Appl. 13, 567–593 (1992)
Parlett, B.N., Taylor, D.R., Liu, Z.A.: A look-ahead Lanczos algorithm for unsymmetric matrices. Math. Comput. 44(169), 105–124 (1985)
Pozza, S., Pranic, M.S.: The Gauss quadrature for general linear functionals, Lanczos algorithm, and minimal partial realization. Numer. Algorithms 88(2), 647–678 (2021)
Saad, Y.: Iterative methods for sparse linear systems. The PWS Publishing Company, Boston, 1996. 2nd edition, SIAM, Philadelphia (2003)
Saad, Y., Schultz, M.H.: GMRES: a generalized minimal residual algorithm for solving non-symmetric linear systems. SIAM J. Sci Stat. Comput. 7, 856–869 (1986)
Sadok, H.: Méthods de projection pour les systèmes linéaires et non linéaires. Habilitation thesis, University of Lille (1994)
Sadok, H.: CMRH: a new method for solving nonsymmetric linear systems based on the Hessenberg reduction algorithm. Numer. Algorithms 20, 303–321 (1999)
Sadok, H., Szyld, D.: A new look at CMRH and its relation to GMRES. BIT Numer. Math. 52, 485–501 (2012)
Sonneveld, P.: CGS: a fast Lanczos-type solver for non-symmetric linear systems. SIAM J. Sci. Stat. Comput. 10, 36–52 (1989)
Taylor, D.R.: Analysis of the look ahead Lanczos algorithm. Ph.D. thesis, University of California, Berkley (1982)
Van Der Vorst, H.A.: Bi-CGStab: a fast and smoothy converging variant of Bi-CG for the solution of non-symmetric linear systems. SIAM J. Sci. Stat. Comput. 12, 631–644 (1992)
Van der Vorst, H.A.: Iterative Krylov methods for large linear systems. Cambridge University Press, Cambridge (2003)
Wilkinson, J.H.: The algebraic eigenvalue problem. Claredon Press, Oxford, England (1965)
Acknowledgements
The authors would like to thank the referees for their constructive comments. Their remarks have helped us to improve the presentation of this paper.
Funding
None.
Author information
Authors and Affiliations
Contributions
All three authors have contributed in the same way.
Corresponding author
Ethics declarations
Ethical approval
Not applicable. External Review board.
Competing interests
The authors declare no competing interests.
Conflict of interest
The authors declare that they have no conflict of interest.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Bouyghf, F., Messaoudi, A. & Sadok, H. A unified approach to Krylov subspace methods for solving linear systems. Numer Algor 96, 305–332 (2024). https://doi.org/10.1007/s11075-023-01648-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11075-023-01648-0