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

Barrett, Richard/ Berry, Michael W./ Chan, Tony F.

Society for Industrial & Applied Mathematics,U.S.（1994/03発売）

• 製本 Paperback:紙装版/ペーパーバック版／ページ数 141 p.
• 言語 ENG
• 商品コード 9780898713282
• DDC分類 519.72

Full Description

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.

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.