Elsevier S & T

Krylov Solvers for Linear Algebraic Systems: Krylov Solvers

Broyden, Charles George; Vespucci, Maria Teresa

In stock
No reviews
87.000 KD inc. VAT
License
Table of contents
  • Cover
  • Prefacevii
  • Contentsix
  • 1. Introduction1
  • Norm-Reducing Methods3
  • The Quasi-Minimal Residual (QMR) Technique8
  • Projection Methods10
  • Matrix Equations12
  • Some Basic Theory13
  • The Naming of Algorithms17
  • Historical Notes18
  • 2. The Long Recurrences21
  • The Gram-Schmidt Method22
  • Causes of Breakdown*24
  • Discussion and Summary26
  • Arnoldi's Method28
  • OrthoDir and GCR32
  • FOM, GMRes and MinRes35
  • Practical Considerations39
  • 3. The Short Recurrences43
  • The Block-CG Algorithm (BICG)43
  • Alternative Forms45
  • The Original Lanczos Method47
  • Simple and Compound Algorithms48
  • Galerkin Algorithms51
  • The Conjugate Gradient Algorithm (CG)51
  • The Biconjugate Gradient Algorithm (BiCG)52
  • The BiCGL Algorithm53
  • The Hegedus "Galerkin" Algorithm (HGL)54
  • The Hegedus "Galerkin" Algorithm (HG)54
  • The Concus-Golub-Widlund Algorithm (CGW)55
  • Minimum-Residual Algorithms57
  • The Conjugate Residual Algorithm (CR)57
  • The Modified Conjugate Residual Algorithm (MCR)58
  • The CG Normal Residuals Algorithm (CGNR)59
  • The Biconjugate Residual Algorithm (BiCR)60
  • The Biconjugate Residual Algorithm (BiCRL)61
  • Minimum-Error Algorithms61
  • The Method of Orthogonal Directions (OD)62
  • The Stabilised OB Method (StOD)63
  • The CG Normal Errors, or Craig's, Algorithm (CGNE)64
  • Lanczos-Based Methods64
  • SymmLQ65
  • LSQR and LSQR267
  • QMR (Original Version but Without Look-Ahead)69
  • Existence of Short Recurrences*70
  • 4. The Krylov Aspects77
  • Equivalent Algorithms84
  • Rates of Convergence87
  • More on GMRes91
  • Special Cases*99
  • BiCG and BiCGL99
  • QMR102
  • 5. Transpose-Free Methods105
  • The Conjugate-Gradient Squared Method (CGS)105
  • BiCGStab109
  • Other Algorithms113
  • Discussion114
  • 6. More on QMR117
  • The Implementation of QMR, GMRes, SymmLQ and LSQR117
  • QMRBiCG - An Alternative Form of QMR Without Look-Ahead120
  • Simplified (Symmetric) QMR122
  • QMR and BiCG125
  • QMR and MRS126
  • Discussion131
  • 7. Look-Ahead Methods133
  • Note on Notation136
  • The Computational Versions137
  • The Look-Ahead Block Lanczos Algorithm138
  • The Hestenes-Stiefel Version139
  • Particular Algorithms142
  • More Krylov Aspects*145
  • Practical Details148
  • 8. General Block Methods151
  • Multiple Systems151
  • Single Systems157
  • 9. Some Numerical Considerations163
  • 10. And in Practice...?173
  • Presenting the Results175
  • Choosing the Examples176
  • Computing the Residuals178
  • Scaling and Starting180
  • Types of Failure182
  • Heads Over the Parapet183
  • HS Versus Lanczos183
  • Galerkin Versus Minimum Residual186
  • Do We Need Residual Smoothing?187
  • Do We Need Look-Ahead?188
  • Do We Need Preconditioning?189
  • Do We Need Sophisticated Linear Algebra?189
  • And the Best Algorithms...?189
  • For Symmetric Systems192
  • 11. Preconditioning193
  • Galerkin Methods195
  • Minimum Residual Methods*203
  • Notation (Again)207
  • Polynomial Preconditioning207
  • An Early Example208
  • General Polynomial Preconditioning208
  • Neumann Preconditioning210
  • Chebychev Preconditioning212
  • Other Polynomial Preconditioners215
  • Some Non-Negative Matrix Theory219
  • (S)SOR Preconditioners226
  • SSOR230
  • ILU Preconditioning231
  • Incomplete Cholesky (IC) Preconditioning233
  • DCR235
  • ILU(p)235
  • Threshold Variants (ILUT)243
  • Imposing Symmetry249
  • Tismenetsky's Method250
  • Numerical Considerations252
  • ILU(p) Versus ILUT256
  • The Impact of Re-Ordering257
  • Methods for Parallel Computers262
  • The AIM Methods (SpAI, MR and MRP)263
  • The AIF Methods (FSAI, AIB and AInv)267
  • AIB267
  • AInv and SAInv268
  • The PP Methods (JP and the TN Methods)270
  • The AIAF Methods271
  • Other Methods271
  • General Survey274
  • In Conclusion277
  • 12. Duality279
  • Interpretations284
  • Appendix A Reduction of upper Hessenberg matrix to upper triangular form287
  • Appendix B Schur complements293
  • Appendix C The Jordan Form295
  • Appendix D Chebychev polynomials297
  • Appendix E The companion matrix299
  • Appendix F The algorithms301
  • Appendix G Guide to the graphs313
  • References315
  • Index327
Book details
  • Vendor Elsevier S & T
  • SKU 9780444514745
  • ISBN-13 9780080478876
  • Author Broyden, Charles George; Vespucci, Maria Teresa
  • Category Mathematics
  • Subject Linear

Do you have questions about this book?

Ask an expert!

Description eBook delivery & access Reviews
The first four chapters of this book give a comprehensive and unified theory of the Krylov methods. Many of these are shown to be particular examples of
the block conjugate-gradient algorithm and it is this observation that
permits the unification of the theory. The two major sub-classes of those
methods, the Lanczos and the Hestenes-Stiefel, are developed in parallel as
natural generalisations of the Orthodir (GCR) and Orthomin algorithms. These
are themselves based on Arnoldi's algorithm and a generalised Gram-Schmidt
algorithm and their properties, in particular their stability properties,
are determined by the two matrices that define the block conjugate-gradient
algorithm. These are the matrix of coefficients and the preconditioning
matrix.

In Chapter 5 the"transpose-free" algorithms based on the conjugate-gradient squared algorithm are presented while Chapter 6 examines the various ways in which the QMR technique has been exploited. Look-ahead methods and general block methods are dealt with in Chapters 7 and 8 while Chapter 9 is devoted to error analysis of two basic algorithms.

In Chapter 10 the results of numerical testing of the more important algorithms in their basic forms (i.e. without look-ahead or preconditioning) are presented and these are related to the structure of the algorithms and the general theory. Graphs illustrating the performances of various algorithm/problem combinations are given via a CD-ROM.

Chapter 11, by far the longest, gives a survey of preconditioning techniques. These range from the old idea of polynomial preconditioning via SOR and ILU preconditioning to methods like SpAI, AInv and the multigrid methods that were developed specifically for use with parallel computers. Chapter 12 is devoted to dual algorithms like Orthores and the reverse algorithms of Hegedus. Finally certain ancillary matters like reduction to Hessenberg form, Chebychev polynomials and the companion matrix are described in a series of appendices.

· comprehensive and unified approach
· up-to-date chapter on preconditioners
· complete theory of stability
· includes dual and reverse methods
· comparison of algorithms on CD-ROM
· objective assessment of algorithms