Next Page: How to Use This Book

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

Richard Barrett , Michael Berry [utk-thanks], Tony F. Chan ,
James Demmel , June Donato , Jack Dongarra [utk-thanks] [ornl-thanks],
Victor Eijkhout [utk-thanks], Roldan Pozo [utk-thanks], Charles Romine [ornl-thanks],
and Henk Van der Vorst

• How to Use This Book
• Acknowledgements
• Contents
• List of Figures
• Introduction
  • Why Use Templates?
  • What Methods Are Covered?
• Iterative Methods
  • Overview of the Methods
  • Stationary Iterative Methods
    • The Jacobi Method
      • Convergence of the Jacobi method
    • The Gauss-Seidel Method
    • The Successive Overrelaxation Method
      • Choosing the Value of
    • The Symmetric Successive Overrelaxation Method
    • Notes and References
  • Nonstationary Iterative Methods
    • 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)
      • Theory
      • Implementation
    • BiConjugate Gradient (BiCG)
      • Convergence
      • Implementation
    • Quasi-Minimal Residual (QMR)
      • Convergence
      • Implementation
    • Conjugate Gradient Squared Method (CGS)
      • Convergence
      • Implementation
    • BiConjugate Gradient Stabilized (Bi-CGSTAB)
      • Convergence
      • Implementation
    • Chebyshev Iteration
      • Comparison with other methods
      • Convergence
      • Implementation
  • Summary of the Methods
  • A short history of Krylov methods
  • Survey of recent Krylov methods
• Preconditioners
  • The why and how
    • Cost trade-off
    • Theoretical prerequisites on preconditioners
  • Jacobi Preconditioning
    • Block Jacobi Methods
    • Discussion
  • SSOR preconditioning
  • Incomplete Factorization Preconditioners
    • Creating an incomplete factorization
    • Point incomplete factorizations
      • Special cases: central differences
      • Modified incomplete factorizations
      • Parallelism aspects
    • Block factorization methods
      • 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
    • 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
    • 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
    • Sparse Incomplete Factorizations
      • Generating a CRS-based Incomplete Factorization
      • CRS-based Factorization Solve
      • CRS-based Factorization Transpose Solve
  • Parallelism
    • Inner products
      • Overlapping communication and computation
      • Fewer synchronization points
    • Vector updates
    • 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 Iterative Methods
  • Reduced System Preconditioning
  • Domain Decomposition Methods
    • Overlapping Subdomain Methods
    • Non-overlapping Subdomain Methods
    • Multiplicative Schwarz Methods
      • Inexact Solves
      • Nonsymmetric Problems
      • Choice of Coarse Grid Size
  • Multigrid Methods
  • Row Projection Methods
• Obtaining the Software
• Overview of the BLAS
• Glossary
• Notation
• References
• Index
• About this document ...