Footnotes How to Use This Book Overview of the Methods Sparse Incomplete Factorizations Generating a CRS-based - Incomplete Factorization CRS-based Factorization Solve CRS-based Factorization Transpose Solve Generating a CRS-based Incomplete Factorization Parallelism Inner products Overlapping communication and computation Fewer synchronization points Vector updates Stationary Iterative Methods Matrix-vector products Preconditioning Discovering parallelism in sequential preconditioners. More parallel variants of sequential preconditioners. Fully decoupled preconditioners. Wavefronts in the Gauss-Seidel and Conjugate Gradient methods Blocked operations in the GMRES method Remaining topics The Lanczos Connection Block and -step Iterative Methods The Jacobi Method Reduced System Preconditioning Domain Decomposition Methods Overlapping Subdomain Methods Non-overlapping Subdomain Methods Further Remarks Multiplicative Schwarz Methods Inexact Solves Nonsymmetric Problems Choice of Coarse Grid Size Multigrid Methods Convergence of the Jacobi method Row Projection Methods Obtaining the Software Overview of the BLAS Glossary Notation References Index About this document ... The Gauss-Seidel Method The Successive Overrelaxation Method Choosing the Value of The Symmetric Successive Overrelaxation Method Notes and References Nonstationary Iterative Methods Author's Affiliations Conjugate Gradient Method (CG) Theory Convergence Implementation Further references MINRES and SYMMLQ Theory CG on the Normal Equations, CGNE and CGNR Theory Generalized Minimal Residual (GMRES) Acknowledgments Theory Implementation BiConjugate Gradient (BiCG) Convergence Implementation Quasi-Minimal Residual (QMR) Convergence Implementation Conjugate Gradient Squared Method (CGS) Convergence Contents Implementation BiConjugate Gradient Stabilized (Bi-CGSTAB) Convergence Implementation Chebyshev Iteration Comparison with other methods Convergence Implementation Computational Aspects of the Methods A short history of Krylov methods List of Figures Survey of recent Krylov methods Preconditioners The why and how Cost trade-off Left and right preconditioning Jacobi Preconditioning Block Jacobi Methods Discussion SSOR preconditioning Incomplete Factorization Preconditioners Introduction Creating an incomplete factorization Solving a system with an incomplete factorization preconditioner Point incomplete factorizations Fill-in strategies Simple cases: and - Special cases: central differences Modified incomplete factorizations Vectorization of the preconditioner solve Parallelizing the preconditioner solve Block factorization methods Why Use Templates? The idea behind block factorizations Approximate inverses The special case of block tridiagonality Two types of incomplete block factorizations Blocking over systems of partial differential equations Incomplete LQ factorizations Polynomial preconditioners Preconditioners from properties of the differential equation Preconditioning by the symmetric part The use of fast solvers What Methods Are Covered? Alternating Direction Implicit methods 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 Iterative Methods Survey of Sparse Matrix Storage Formats Compressed Row Storage (CRS) Compressed Column Storage (CCS) Block Compressed Row Storage (BCRS) Compressed Diagonal Storage (CDS) Jagged Diagonal Storage (JDS) Skyline Storage (SKS) Matrix vector products CRS Matrix-Vector Product CDS Matrix-Vector Product Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods