=25pt

-8pt

Eijk-hout

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

Richard Barrett ,Michael Berry, Tony F. Chan ,
James Demmel , June M. Donato , Jack Dongarra ,
Victor Eijkhout , Roldan Pozo Charles Romine ,
and Henk Van der Vorst

This book is also available in Postscript from over the Internet.
To retrieve the postscript file you can use one of the following methods:

1. anonymous ftp to www.netlib.org
   cd templates
   get templates.ps
   quit

2. from any machine on the Internet type:
   rcp anon@www.netlib.org:templates/templates.ps templates.ps

3. send email to netlib@ornl.gov and in the message type:
   send templates.ps from templates

The url for this book is http://www.netlib.org/templates/Templates.html .

A bibtex reference for this book follows: @BOOK{templates, AUTHOR = {R. Barrett and M. Berry and T. F. Chan and J. Demmel and J. Donato and J. Dongarra and V. Eijkhout and R. Pozo and C. Romine, and H. Van der Vorst }, TITLE = {Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods}, PUBLISHER = {SIAM}, YEAR = {1994}, ADDRESS = {Philadelphia, PA} }

• How to Use This Book
• Author's Affiliations
• Acknowledgments
• 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
  • Computational Aspects of the Methods
  • A short history of Krylov methods
  • 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
    • 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
      • 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
      • Generating a CRS-based Incomplete Factorization
  • 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 and -step Iterative Methods
  • 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
  • Row Projection Methods
• Obtaining the Software
• Overview of the BLAS
• Glossary
• Notation
• References
• Index
• About this document ...