Krylov Subspace Methods: Principles and Analysis
The mathematical theory of Krylov subspace methods with a focus on solving systems of linear algebraic equations is given a detailed treatment in this principles-based book. Starting from the idea of projections, Krylov subspace methods are characterised by their orthogonality and minimisation properties. Projections onto highly nonlinear Krylov subspaces can be linked with the underlying problem of moments, and therefore Krylov subspace methods can be viewed as matching moments model reduction. This allows enlightening reformulations of questions from matrix computations into the language of orthogonal polynomials, Gauss-Christoffel quadrature, continued fractions, and, more generally, of Vorobyev's method of moments. Using the concept of cyclic invariant subspaces, conditions are studied that allow the generation of orthogonal Krylov subspace bases via short recurrences. The results motivate the important practical distinction between Hermitian and non-Hermitian problems. Finally, the book thoroughly addresses the computational cost while using Krylov subspace methods. The investigation includes effects of finite precision arithmetic and focuses on the method of conjugate gradients (CG) and generalised minimal residuals (GMRES) as major examples. There is an emphasis on the way algebraic computations must always be considered in the context of solving real-world problems, where the mathematical modelling, discretisation and computation cannot be separated from each other. The book also underlines the importance of the historical context and demonstrates that knowledge of early developments can play an important role in understanding and resolving very recent computational problems. Many extensive historical notes are included as an inherent part of the text as well as the formulation of some omitted issues and challenges which need to be addressed in future work. This book is applicable to a wide variety of graduate courses on Krylov subspace methods and related subjects, as well as benefiting those interested in the history of mathematics.
2 Krylov Subspace Methods
3 Matching Moments and Model Reduction View
4 Short Recurrences for Generating Orthogonal Krylov Subspace Bases
5 Cost of Computations Using Krylov Subspace Methods
Other editions - View all
algebraic error Anal analysis Appl applied Arnoldi algorithm backward error basis vectors behaviour bound CG computations CG method Chapter Chebyshev Chebyshev polynomials condition number conjugate gradient consider context continued fractions convergence corresponding cyclic subspace decomposition defined distribution function dmin(A eigenvalues eigenvectors equations equivalent exact arithmetic factorisation finite precision Gauss Gauss–Christoffel quadrature given inner product GMRES grade Hermitian Lanczos algorithm Hessenberg Hestenes and Stiefel HPD matrix initial residual initial vector inner product integral iterative computations iterative methods Jacobi matrix Krylov subspace methods Lanczos algorithm Lemma linear algebraic systems linear systems Math mathematical minimal polynomial minimisation model reduction monic n-node nodes nonsingular nonzero notation numerical Numerical Analysis numerical stability optimal orthogonal polynomials orthogonalisation orthonormal paper problem projection process proof residual norm respect right-hand side Ritz values rounding errors Section SIAM step Stieltjes symmetric Theorem three-term recurrence tion vectors v1