Iterative Methods for Solving Linear Systems

Much recent research has concentrated on the efficient solution of large sparse or structured linear systems using iterative methods. A language loaded with acronyms for a thousand different algorithms has developed, and it is often difficult even for specialists to identify the basic principles involved. Here is a book that focuses on the analysis of iterative methods. The author includes the most useful algorithms from a practical point of view and discusses the mathematical principles behind their derivation and analysis. Several questions are emphasized throughout: Does the method converge? If so, how fast? Is it optimal, among a certain class? If not, can it be shown to be near-optimal? The answers are presented clearly, when they are known, and remaining important open questions are laid out for further study.

Spis treści:
List of Algorithms
Preface
1. Introduction. Brief Overview of the State of the Art
Notation
Review of Relevant Linear Algebra
Part I. Krylov Subspace Approximations. 2. Some Iteration Methods. Simple Iteration
Orthomin(1) and Steepest Descent
Orthomin(2) and CG
Orthodir, MINRES, and GMRES
Derivation of MINRES and CG from the Lanczos Algorithm
3. Error Bounds for CG, MINRES, and GMRES. Hermitian Problems-CG and MINRES
Non-Hermitian Problems-GMRES
4. Effects of Finite Precision Arithmetic. Some Numerical Examples
The Lanczos Algorithm
A Hypothetical MINRES/CG Implementation
A Matrix Completion Problem
Orthogonal Polynomials
5. BiCG and Related Methods. The Two-Sided Lanczos Algorithm
The Biconjugate Gradient Algorithm
The Quasi-Minimal Residual Algorithm
Relation Between BiCG and QMR
The Conjugate Gradient Squared Algorithm
The BiCGSTAB Algorithm
Which Method Should I Use?
6. Is There A Short Recurrence for a Near-Optimal Approximation? The Faber and Manteuffel Result
Implications
7. Miscellaneous Issues. Symmetrizing the Problem
Error Estimation and Stopping Criteria
Attainable Accuracy
Multiple Right-Hand Sides and Block Methods
Computer Implementation
Part II. Preconditioners. 8. Overview and Preconditioned Algorithms. 9. Two Example Problems. The Diffusion Equation
The Transport Equation
10. Comparison of Preconditioners. Jacobi, Gauss--Seidel, SOR
The Perron--Frobenius Theorem
Comparison of Regular Splittings
Regular Splittings Used with the CG Algorithm
Optimal Diagonal and Block Diagonal Preconditioners
11. Incomplete Decompositions. Incomplete Cholesky Decomposition
Modified Incomplete Cholesky Decomposition
12. Multigrid and Domain Decomposition Methods. Multigrid Methods
Basic Ideas of Domain Decomposition Methods.