Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods

In this book, which focuses on the use of iterative methods for solving large sparse systems of linear equations, templates are introduced to meet the needs of both the traditional user and the high performance specialist. Templates, a description of a general algorithm rather than the executable object or source code more commonly found in a conventional software library, offer whatever degree of customization the user may desire. Templates have three distinct advantages: they are general and reusable, they are not language specific, and they exploit the expertise of both the numerical analyst, who creates a template reflecting in depth knowledge of a specific numerical technique, and the computational scientist, who then provides ""value added"" capability to the general template description, customizing it for specific needs. For each template that is presented, the authors provide a mathematical description of the flow of the algorithm, discussion of convergence and stopping criteria to use in the iteration, suggestions for applying a method to special matrix types, advice for tuning the template, tips on parallel implementations, and hints as to when and why a method is useful.

Table of Contents:
List of Symbols List of Figures Chapter 1: Introduction Why Use Templates? What Methods Are Covered? Chapter 2: Iterative Methods Overview of the Methods Stationary Iterative Methods The Jacobi Method The Gauss-Seidel Method The Successive Overrelaxation Method The Symmetric Successive Overrelaxation Method Notes and References Nonstationary Iterative Methods Conjugate Gradient Method (CG) MINRES and SYMMLQ CG on the Normal Equations, CGNE and CGNR Generalized Minimal Residual (GMRES) BiConjugate Gradient (BiCG) Quasi-Minimal Residual (QMR) Conjugate Gradient Squared Method (CGS) BiConjugate Gradient Squared Method (Bi-CGSTAB) Chebyshev Iteration Computational Aspects of the Methods A Short History of Krylov Methods Survey of Recent Krylov Methods Chapter 3: Preconditioners The Why and How Cost Trade-off Left and right preconditioning Jacobi Preconditioning Block Jacobi Methods Discussion SSOR Preconditioning Incomplete Factorization Preconditioners Creating an Incomplete Factorization Point Incomplete Factorizations Block Factorization Methods Incomplete LQ Factorization Polynomial Preconditioners Other Preconditioners Preconditioning by the Symmetric Part The Use of Fast Solvers Alternating Direction Implicit Methods Chapter 4: Related Issues Complex Systems Stopping Criteria More Details about Stopping Criteria When __ or ____ is not Readily Available Estimating ____ Stopping When Progress is no Longer Being Made Accounting for Floating Point Errors Data Structures Survey of Sparse Matrix Storage Formats Matrix Vector Products Sparse Incomplete Factorizations Parallelism Inner Products Vector Updates Matrix-vector Products Preconditioning Wavefronts in the Gauss-Seidel and Conjugate Gradient Methods Blocked Operations in the GMRES Method Chapter 5: Remaining Topics The Lanczos Connection Block and n - step Iterative Methods Reduced System Preconditioning Domain Decomposition Methods Overlapping Subdomain Methods Non-overlapping Subdomain Methods Further Remarks Multigrid Methods Row Projection Methods Appendix A: Obtaining the Software Appendix B: Overview of the Blas Appendix C: Glossary.