Contents
Next:
List of Figures
Up:
Templates for the Solution
Previous:
Acknowledgments
Contents
How to Use This Book
Author's Affiliations
Acknowledgments
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 ...
Jack Dongarra
Mon Nov 20 08:52:54 EST 1995