Table of Contents
Springer Nature


KRYLOV METHODS
FOR NONSYMMETRIC LINEAR SYSTEMS

Gérard MEURANT
and Jurjen DUINTJER TEBBENS

Springer
2020
ISBN 978-3-030-55250-3
686 pages



This book gives an overview of the state-of-the-art of Krylov subspace iterative methods for solving nonsymmetric systems of algebraic linear equations. The mathematical properties of the methods are described and analyzed including well-known convergence results, along with their behavior in finite precision arithmetic. A number of numerical examples demonstrate the properties and the behavior of the described methods. Also considered are the methods’ implementations and coding as Matlab-like functions. Methods which became popular recently are considered in the general framework of Q-OR (quasi-orthogonal )/Q-MR (quasi-minimum) residual methods.

  • Errata (PDF) [download]



  • Table of Contents (PDF) [download]

    Table of Contents

    1/ Introduction [TOC]

    

    2/ Notation, definitions and tools  [TOC]
    

    2.1 Notation, basic matrix types and properties . . . . . . . . . . . . . . . . . . 13
2.2 Eigenvalues and eigenvectors . . . . . . . . . . . . . . . . . . . . . . . . . .16
2.3 The Jordan canonical form . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.4 Minimal polynomials. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .19
2.5 Singular values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.6 The companion matrix. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.7 Hessenberg matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.8 Tridiagonal matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .31
2.9 Unitary transformations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.10 Krylov subspaces and their basic properties . . . . . . . . . . . . . . . . . .40
2.11 Finite precision arithmetic and backward stability . . . . . . . . . . . . . . 43
2.12 Parallel computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.13 Preconditioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .47
2.14 Stopping criterion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.15 Historical notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

    

    3/ Q-OR and Q-MR methods  [TOC]
    

    3.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .53
3.2 Relations between Q-OR and the associated Q-MR process . . . . . . . . . . . . .58
3.3 Residual vectors and residual polynomials . . . . . . . . . . . . . . . . . . . 63
3.4 The inverse of Uk and the residual norms . . . . . . . . . . . . . . . . . . . .73
3.5 Prescribing the convergence curve . . . . . . . . . . . . . . . . . . . . . . . 77
3.6 Stagnation of Q-MR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .82
3.7 Residual bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
3.8 Residual norms in terms of spectral quantities . . . . . . . . . . . . . . . . .85
3.9 Relations between Q-OR/Q-MR methods with different bases . . . . . . . . . . . .89
3.10 Generalized Q-OR/Q-MR methods . . . . . . . . . . . . . . . . . . . . . . . . .92
3.11 Historical notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

    

    4/Bases for Krylov subspaces  [TOC]
    

    4.1 Orthonormal basis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
4.2 Hessenberg basis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
4.3 Biorthogonal basis. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .112
4.4 The generalized Hessenberg process . . . . . . . . . . . . . . . . . . . . . . 118
4.5 Q-OR optimal basis. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .119
4.6 Newton and Chebyshev bases . . . . . . . . . . . . . . . . . . . . . . . . . . 133
4.7 Truncated bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .137
4.8 Parallel computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
4.9 Finite precision arithmetic and numerical experiments . . . . . . . . . . . . .149
     4.9.1 Orthogonal basis . . . . . . . . . . . . . . . . . . . . . . . . . . . .149
     4.9.2 Hessenberg basis . . . . . . . . . . . . . . . . . . . . . . . . . . . .167
     4.9.3 Biorthogonal basis . . . . . . . . . . . . . . . . . . . . . . . . . . .167
     4.9.4 Q-OR opt basis. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
     4.9.5 Newton and Chebyshev bases . . . . . . . . . . . . . . . . . . . . . . .180
     4.9.6 Truncated Q-OR basis . . . . . . . . . . . . . . . . . . . . . . . . . .181
4.10 Historical notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .188

    

    5/ FOM/GMRES and variants  [TOC]
    

    5.1 Introduction to FOM and GMRES . . . . . . . . . . . . . . . . . . . . . . . . .193
5.2 Convergence of FOM and GMRES . . . . . . . . . . . . . . . . . . . . . . . . . 197
5.3 Prescribed convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
5.4 Stagnation of GMRES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .216
5.5 Residual norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
5.6 The residual polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
5.7 Study of convergence using unitary matrices . . . . . . . . . . . . . . . . . .241
5.8 Estimates of the norm of the error . . . . . . . . . . . . . . . . . . . . . . 251
5.9 Other implementations of GMRES . . . . . . . . . . . . . . . . . . . . . . . . 263
5.10 Parallel computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .269
5.11 Finite precision arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . 273
5.12 Numerical examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .278
       5.12.1 FOM and GMRES . . . . . . . . . . . . . . . . . . . . . . . . . . . .278
       5.12.2 Variants of GMRES . . . . . . . . . . . . . . . . . . . . . . . . . .281
       5.12.3 Prescribed convergence and stagnation . . . . . . . . . . . . . . . .288
       5.12.4 Residual norm bounds. . . . . . . . . . . . . . . . . . . . . . . . .290
       5.12.5 Error norm estimates . . . . . . . . . . . . . . . . . . . . . . . . 292
5.13 Historical notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .292

    

    6/ Methods equivalent to FOM or GMRES  [TOC]
    

    6.1 GCR, Orthomin, Orthodir and Axelsson’s method . . . . . . . . . . . . . . . . .303
6.2 Simpler, residual-based simpler and adaptive simpler GMRES . . . . . . . . . . 309
6.3 Orthores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319
6.4 Q-OR Optinv . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .320
6.5 Parallel computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323
6.6 Finite precision arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . .324
6.7 Numerical examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327
      6.7.1 GCR, Orthodir and Axelsson . . . . . . . . . . . . . . . . . . . . . . 327
      6.7.2 ASGMRES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .330
      6.7.3 FOM and Orthores . . . . . . . . . . . . . . . . . . . . . . . . . . . 334
      6.7.4 Q-OR Optinv . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .335
6.8 Historical notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338

    

    7/ Hessenberg/CMRH  [TOC]
    

    7.1 Derivation of the methods . . . . . . . . . . . . . . . . . . . . . . . . . . .341
7.2 Comparison with GMRES and convergence of CMRH . . . . . . . . . . . . . . . . .346
7.3 Prescribed convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347
7.4 Stagnation of CMRH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348
7.5 Residual norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348
7.6 Parallel computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348
7.7 Finite precision arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . .349
7.8 Numerical experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . .349
7.9 Historical notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352

    

    8/BiCG/QMR and Lanczos algorithms  [TOC]
    

    8.1 The Lanczos algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 355
8.2 Derivation of BiCG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358
8.3 QMR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .368
8.4 Breakdowns and look-ahead in BiCG/QMR . . . . . . . . . . . . . . . . . . . . .373
8.5 Comparison of QMR and GMRES. . . . . . . . . . . . . . . . . . . . . . . . . . 378
8.6 Prescribed convergence in BiCG and QMR . . . . . . . . . . . . . . . . . . . . 379
8.7 Residual norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 382
8.8 Lanczos algorithms with look-ahead and formal orthogonal polynomials . . . . . 383
8.9 Parallel computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 389
8.10 Finite precision arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . 391
8.11 Numerical examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .394
       8.11.1 BiCG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394
       8.11.2 QMR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .396
       8.11.3 Comparisons with GMRES . . . . . . . . . . . . . . . . . . . . . . . 402
       8.11.4 Methods with look-ahead . . . . . . . . . . . . . . . . . . . . . . .403
       8.11.5 Ai/Bj . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .404
8.12 Historical notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .405

    

    9/ Transpose-free Lanczos methods  [TOC]
    

    9.1 CGS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .411
9.2 BiCGStab and extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . .421
9.3 Other product-type methods . . . . . . . . . . . . . . . . . . . . . . . . . . 430
9.4 Look-ahead for transpose-free methods. . . . . . . . . . . . . . . . . . . . . 433
9.5 Parallel computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434
9.6 Finite precision arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . .435
9.7 Numerical experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . .436
      9.7.1 BiCGS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .436
      9.7.2 BiCGStab and variants . . . . . . . . . . . . . . . . . . . . . . . . .437
      9.7.3 QMR-like methods . . . . . . . . . . . . . . . . . . . . . . . . . . . 445
9.8 Historical notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 448

    

    10/The IDR family  [TOC]
    

    10.1 The primitive IDR algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 455
10.2 The first IDR algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 456
10.3 IDR(s) and variants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460
10.4 Other IDR algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . .466
10.5 Using higher order stabilizing polynomials . . . . . . . . . . . . . . . . . .471
10.6 Residual norms and convergence . . . . . . . . . . . . . . . . . . . . . . . .475
10.7 A predecessor of IDR: ML(k)BiCGStab . . . . . . . . . . . . . . . . . . . . . 476
10.8 Parallel computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .477
10.9 Finite precision arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . 478
10.10 Numerical examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 478
         10.10.1 IDR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 478
         10.10.2 Variants of IDR and IDR-QMR. . . . . . . . . . . . . . . . . . . .482
         10.10.3 ML(k)BiCGStab . . . . . . . . . . . . . . . . . . . . . . . . . . 485
10.11 Historical notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 488

    

    11/ Restart, deflation and truncation  [TOC]
    

    11.1 Restarted FOM and GMRES . . . . . . . . . . . . . . . . . . . . . . . . . . . 498
11.2 Prescribed convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . .505
11.3 Restarting techniques for FOM and GMRES . . . . . . . . . . . . . . . . . . . 515
11.4 Restarted and augmented CMRH and Q-OR Opt . . . . . . . . . . . . . . . . . . 535
11.5 Truncated FOM and GMRES . . . . . . . . . . . . . . . . . . . . . . . . . . . 535
11.6 Truncated Q-OR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .538
11.7 Parallel computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .539
11.8 Finite precision arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . 539
11.9 Numerical experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . 539
       11.9.1 Restarted GMRES without preconditioning . . . . . . . . . . . . . . .539
       11.9.2 Restarted GMRES with preconditioning . . . . . . . . . . . . . . . . 543
       11.9.3 Restarting with deflation and augmentation
                 without preconditioning. . . . . . . . . . . . . . . . . . . . . .545
       11.9.4 Restarting with deflation and augmentation
                 with preconditioning . . . . . . . . . . . . . . . . . . . . . . .562
       11.9.5 Truncated Q-OR . . . . . . . . . . . . . . . . . . . . . . . . . . . 571
11.10 Historical notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 575

    

    12/ Related topics  [TOC]
    

    12.1 FGMRES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .579
12.2 GCRO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .581
12.3 Relaxation for matrix–vector products . . . . . . . . . . . . . . . . . . . . 583
12.4 Systems with multiple right-hand sides . . . . . . . . . . . . . . . . . . . .583
12.5 Shifted linear systems . . . . . . . . . . . . . . . . . . . . . . . . . . . .588
12.6 Singular systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .589
12.7 Least squares problems . . . . . . . . . . . . . . . . . . . . . . . . . . . .590
12.8 Ill-posed problems. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 593
12.9 Eigenvalue computations and rational Krylov methods . . . . . . . . . . . . . 595
12.10 Functions of matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . .596
12.11 Minimum error methods . . . . . . . . . . . . . . . . . . . . . . . . . . . .598
12.12 Residual replacement techniques . . . . . . . . . . . . . . . . . . . . . . .598
12.13 Residual smoothing techniques . . . . . . . . . . . . . . . . . . . . . . . .600
12.14 Hybrid methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 600
12.15 CGNE and CGNR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .601
12.16 USYMLQ and USYMQR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .602

    

    13/ Numerical comparisons of methods  [TOC]
    

    13.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .603
13.2 Small matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .604
13.3 Larger matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 616

    

    References  [TOC]
    
There are 1039 references.


    

  •  References. [download]


    


    

  •  Color figures (PDF) [download]