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.

  • 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]