Iterative Methods for Solving Linear Systems
Will be published approx. on 30. September 1997
Book
Paperback/Softback
235 pages
978-0-89871-396-1 (ISBN)
Description
Much recent research has concentrated on the efficient solution of large sparse or structured linear systems using iterative methods. A language loaded with acronyms for a thousand different algorithms has developed, and it is often difficult even for specialists to identify the basic principles involved. Here is a book that focuses on the analysis of iterative methods. The author includes the most useful algorithms from a practical point of view and discusses the mathematical principles behind their derivation and analysis. Several questions are emphasized throughout: Does the method converge? If so, how fast? Is it optimal, among a certain class? If not, can it be shown to be near-optimal? The answers are presented clearly, when they are known, and remaining important open questions are laid out for further study.
Greenbaum includes important material on the effect of rounding errors on iterative methods that has not appeared in other books on this subject. Additional important topics include a discussion of the open problem of finding a provably near-optimal short recurrence for non-Hermitian linear systems; the relation of matrix properties such as the field of values and the pseudospectrum to the convergence rate of iterative methods; comparison theorems for preconditioners and discussion of optimal preconditioners of specified forms; introductory material on the analysis of incomplete Cholesky, multigrid, and domain decomposition preconditioners, using the diffusion equation and the neutron transport equation as example problems. A small set of recommended algorithms and implementations is included.
Greenbaum includes important material on the effect of rounding errors on iterative methods that has not appeared in other books on this subject. Additional important topics include a discussion of the open problem of finding a provably near-optimal short recurrence for non-Hermitian linear systems; the relation of matrix properties such as the field of values and the pseudospectrum to the convergence rate of iterative methods; comparison theorems for preconditioners and discussion of optimal preconditioners of specified forms; introductory material on the analysis of incomplete Cholesky, multigrid, and domain decomposition preconditioners, using the diffusion equation and the neutron transport equation as example problems. A small set of recommended algorithms and implementations is included.
Reviews / Votes
'This graduate-level textbook gives equal weights to iterative methods and preconditioning (including domain decomposition and multigrid), and it approaches Krylov space methods from a somewhat different angle. It also treats some subjects that appear for the first time in a textbook, like new results on roundoff effects in the Lanczos and conjugate gradient algorithms. This well-done introduction to the area can be strongly recommended. It is competently written by an author who has contributed much to the complete reshaping of this field in the last twenty years.' Martin H. Gutknecht, ETH Zurich 'For a course in matrix iterations, this is just the right book. It is wide-ranging, careful about details, and appealingly written - a major addition to the literature in this important area.' Nick Trefethen, Professor of Numerical Analysis, Oxford University 'This book differs substantially from other books on iterative methods, including those recently published, in that it concentrates on several principles behind the derivation and analysis of the most important methods and preconditioning techniques. Individual algorithms serve as examples illustrating the discussed ideas. Strong emphasis is given to motivation and its relation to problems in other areas of mathematics. The book speaks in clear language about principal problems in the area of iterative methods. It represents a comprehensive introduction to the field and stimulates the interest of the reader. It is valuable for students and also for experts working in the area of iterative methods.' Zdenek Strakos, Professor, Czech Academy of Sciences, Institute of Computer Science 'Anne Greenbaum is an admired authority in the field of iterative methods. Engineers and scientists often ask me about the puzzling behavior of iterative methods, which I almost always answer with a reference to Anne's work, now made easy to point to in her new book.' Paul Saylor, Department of Computer Science, University of Illinois, Urbana-ChampaignMore details
Series
Language
English
Place of publication
New York
United States
Target group
Professional and scholarly
Product notice
Paperback (trade)
Unsewn / adhesive bound
Dimensions
Height: 253 mm
Width: 178 mm
Thickness: 13 mm
Weight
422 gr
ISBN-13
978-0-89871-396-1 (9780898713961)
Copyright in bibliographic data and cover images is held by Nielsen Book Services Limited or by the publishers or by their respective licensors: all rights reserved.
Schweitzer Classification
Content
List of Algorithms
Preface
Chapter 1: Introduction. Brief Overview of the State of the Art
Notation
Review of Relevant Linear Algebra
Part I: Krylov Subspace Approximations. Chapter 2: Some Iteration Methods. Simple Iteration
Orthomin(1) and Steepest Descent
Orthomin(2) and CG
Orthodir, MINRES, and GMRES
Derivation of MINRES and CG from the Lanczos Algorithm
Chapter 3: Error Bounds for CG, MINRES, and GMRES. Hermitian Problems-CG and MINRES
Non-Hermitian Problems-GMRES
Chapter 4: Effects of Finite Precision Arithmetic. Some Numerical Examples
The Lanczos Algorithm
A Hypothetical MINRES/CG Implementation
A Matrix Completion Problem
Orthogonal Polynomials
Chapter 5: BiCG and Related Methods. The Two-Sided Lanczos Algorithm
The Biconjugate Gradient Algorithm
The Quasi-Minimal Residual Algorithm
Relation Between BiCG and QMR
The Conjugate Gradient Squared Algorithm
The BiCGSTAB Algorithm
Which Method Should I Use?
Chapter 6: Is There A Short Recurrence for a Near-Optimal Approximation? The Faber and Manteuffel Result
Implications
Chapter 7: Miscellaneous Issues. Symmetrizing the Problem
Error Estimation and Stopping Criteria
Attainable Accuracy
Multiple Right-Hand Sides and Block Methods
Computer Implementation
Part II: Preconditioners. Chapter 8: Overview and Preconditioned Algorithms. Chapter 9: Two Example Problems. The Diffusion Equation
The Transport Equation
Chapter 10: Comparison of Preconditioners. Jacobi, Gauss--Seidel, SOR
The Perron--Frobenius Theorem
Comparison of Regular Splittings
Regular Splittings Used with the CG Algorithm
Optimal Diagonal and Block Diagonal Preconditioners
Chapter 11: Incomplete Decompositions. Incomplete Cholesky Decomposition
Modified Incomplete Cholesky Decomposition
Chapter 12: Multigrid and Domain Decomposition Methods. Multigrid Methods
Basic Ideas of Domain Decomposition Methods.
Preface
Chapter 1: Introduction. Brief Overview of the State of the Art
Notation
Review of Relevant Linear Algebra
Part I: Krylov Subspace Approximations. Chapter 2: Some Iteration Methods. Simple Iteration
Orthomin(1) and Steepest Descent
Orthomin(2) and CG
Orthodir, MINRES, and GMRES
Derivation of MINRES and CG from the Lanczos Algorithm
Chapter 3: Error Bounds for CG, MINRES, and GMRES. Hermitian Problems-CG and MINRES
Non-Hermitian Problems-GMRES
Chapter 4: Effects of Finite Precision Arithmetic. Some Numerical Examples
The Lanczos Algorithm
A Hypothetical MINRES/CG Implementation
A Matrix Completion Problem
Orthogonal Polynomials
Chapter 5: BiCG and Related Methods. The Two-Sided Lanczos Algorithm
The Biconjugate Gradient Algorithm
The Quasi-Minimal Residual Algorithm
Relation Between BiCG and QMR
The Conjugate Gradient Squared Algorithm
The BiCGSTAB Algorithm
Which Method Should I Use?
Chapter 6: Is There A Short Recurrence for a Near-Optimal Approximation? The Faber and Manteuffel Result
Implications
Chapter 7: Miscellaneous Issues. Symmetrizing the Problem
Error Estimation and Stopping Criteria
Attainable Accuracy
Multiple Right-Hand Sides and Block Methods
Computer Implementation
Part II: Preconditioners. Chapter 8: Overview and Preconditioned Algorithms. Chapter 9: Two Example Problems. The Diffusion Equation
The Transport Equation
Chapter 10: Comparison of Preconditioners. Jacobi, Gauss--Seidel, SOR
The Perron--Frobenius Theorem
Comparison of Regular Splittings
Regular Splittings Used with the CG Algorithm
Optimal Diagonal and Block Diagonal Preconditioners
Chapter 11: Incomplete Decompositions. Incomplete Cholesky Decomposition
Modified Incomplete Cholesky Decomposition
Chapter 12: Multigrid and Domain Decomposition Methods. Multigrid Methods
Basic Ideas of Domain Decomposition Methods.