Contents
Preface to the Second Edition X111
Preface to the First Edition XVl1
1 Background in Linear AIgebra 1
1. 1 Matrices
1. 2 Square Matrices and Eigenvalues 2
1. 3 Types of Matrices 4
1. 4 Vector Inner Products and Norms 5
1. 5 Matrix Norms 7
1. 6 Subspaces , Range, and Kemel 9
1. 7 Orthogonal Vectors and Subspaces 10
1. 8 Canonical Forms of Matrices 14
1. 8.1 Reduction to the Diagonal Form 15
1. 8.2 The Jordan Canonical Form 15
1. 8.3 The Schur Canonical Form 16
1. 8.4 Application to Powers of Matrices 18
1.9 Normal and Hermitian Matrices 20
1.9.1 Normal Matrices 20
1.9.2 Hermitian Matrices 23
1. 10 Nonnegative Matrices, M -Matrices 25
1.1 1 Positive Definite Matrices 29
1. 12 Projection Operators 32
1. 12.1 Range and Null Space of a Projector 32
1. 12.2 Matrix Representations 34
1.1 2.3 Orthogonal and Oblique Projectors 34
1.12.4 Properties of Orthogonal Projectors 36
1.1 3 Basic Concepts in Linear Systems 37
1.1 3.1 Existβnce of a Solution 37
1.1 3.2 Perturbation Analysis 38
Exercises 39
Notes and References 43
2 Discretization of Partial Differential Equations 45
2.1 Partial Differential 句uations 45
2.1.1 EJ1 iptic Operators 46
2.1.2 The Convection Diffusion Equation 48
2.2 Finite Difference Methods 48
2.2.1 Basic Approximations 48
2.2.2 Difference Schemes for the Laplacian Operator 50
2.2.3 Finite Differenc for One-Dim nsion al Problems 51
2.2.4 Upwind Sch mes 52
2.2.5 nitDifferences for Two-Dimensional Probl ms 54
2.2.6 Fast Poisson Solvers 55
2.3 The Finite Element Method 60
2.4 Mesh Generation a nd Refinement 66
2.5 Finite Volum Method 68
Exercises 71
Notes and References 72
3 Sparse Matrices 73
3.1 Introduction 73
3.2 Graph Representations 75
3.2.1 Graphs and Adjacency Graphs 75
3.2.2 Graph s of PDE Matrices 76
3.3 Permutations and Reorderings 77
3.3.1 Basic Concpts 77
3.3.2 Relations with re Adjacency Graph 79
3.3.3 Common Rorderings 81
3.3.4 Irrducibility 89
3.4 Storage Schemes 89
3.5 Basic Sparse Matrix Oprations 92
3.6 Sparse Direct Solution Methods 93
3.6.1 MD Ordering 93
3.6.2 ND Orderin 94
3.7 Test Problems 94
Exe rcises 97
Notes and Rrefere nces 101
4 Basic Iterative Methods 103
4.1 Jacobi , Gauss-Sidel， and Success ssive Overr laxation 103
4.1.1 Block Relaxation Sch mes 106
4. 1.2 Iteration Matrices and Preconditioning 110
4.2 Converge ncce 111
4.2.1 Gnera l Convergence Result 112
4.2.2 Regular Splittings 115
4.2.3 Diagonally Domin ant Matrices 116
4.2.4 Symmtric Positive Dfinite Matrices 119
4.2.5 Proprty A and Consistent Orderings 119
4.3 Altemating Direction Methods 124
Exercises 126
Notes and References 128
5 Projection Methods 129
5 1 Basic Definitions and Algorithms 129
5. 1.1 General Proj ction Methods 130
5. 1. 2 M atrix Representation 131
5.2 General Theory 132
5.2.1 Two Optimality Results 133
5.2.2 Int erpretation in TIrms of Projectors 134
5.2.3 Gene ral Error Bound 135
5.3 One-Dimensional Projection Procsses 137
5.3.1 Steepest Descent 138
5.3.2 MR Iteration 140
5.3.3 Re si du al Norm Steepest Descent 142
5.4 Additive and Multiplicative Processes 143
Exercises 145
Notes and References 149
6 Krylov Subspace Methods, Part 1 151
6.1 Introduction 151
6.2 Kry lov Subspaces 152
6.3 Amoldi 's Mthod 153
6.3.1 The Basic Algorithm 154
6.3.2 Practical Implementation s 156
6.4 Amoldi 's Method for Linear Systems 159
6.4.1 Variation 1: Restarted FOM 160
6.4.2 Variation 2: 10M and DIOM 161
6.5 Generalized Minimal Re sidual Method 164
6.5.1 The Basic GMRES Algori 由m 164
6.5.2 The Hou seholderVersion 165
6.5.3 Prac tical Implementation I ssus 167
6.5.4 Breakdown of G 1RES 171
6.5.5 Variation 1: Re s tarting 171
6.5.6 Variation 2: Truncated GMRES virsions 172
6.5.7 Relations Between FOM and GMRES 177
6.5.8 Residual Smoothing 181
6.5.9 GMRES for Complex Sy stems 184
6.6 The Symmetric Lanczos Algorithm 185
6.6.1 The Algorithm 185
6.6.2 Relation to Orthogonal Polynomials 186
6.7 The Conjugate GradientAlgorithm 187
6.7.1 Derivation and Th0η 187
6.7.2 Altemative Formulations 191
6.7.3 Eigenv alue Estimates from the CG Coefficients 192
6.8 The Conjugate Residual Method 194
6.9 Generalized Co 時ugate Residual, ORTHOMIN , and ORTHODIR 194
6.10 The Faber-Manteuffel Theorem 196
6.11 Convergence Analysis 198
6.1 1.1 Real Chebyshev Polynomials 199
6.11.2 Complex Chebyshev Polynomials 200
6.11.3 Convergence of the CG Algorithm 203
6.1 1.4 Convergence of GMRES 205
6.1 2 Block Krylov Method s 208
Exercises 212
Notes and Referencs 215
7 Krylov Subspace Methods, Part 11 217
7.1 Lanczos Biorthogonalization 217
7.1.1 The Algorim.217
7.1.2 Practical Implementations 220
7.2 The Lanczos Algorithm for Linear Systems 221
7.3 The Biconjugate Gradient and Quas i-Minimal Re sidual Algorithms 222
7.3.1 The BCG Algorithm 222
7.3.2 QMRAlgorithm 224
7.4 Transpose-Free Variants 228
7.4.1 CGS. 229
7.4.2 BICGSTAB 231
7.4.3 TFQMR 234
Exercises 241
Notes and References 243
8 Methods Related to the Normal Equations 245
8.1 The Normal Eq uations 245
8.2 Row Projection Methods 247
8.2.1 Gau ss-S eidel on the Normal Equations 247
8.2.2 Cimmino's Method 249
8.3 Conjugate Gradient and Normal Equations 251
8.3.1 CGNR 252
8.3.2 CGNE 253
8.4 Saddle-Point Problems 254
Exercises 257
N otes and References 259
9 Preconditioned Iterations 261
9.1 Introduction 261
9.2 Preconditioned Conjugate Gradient 262
9.2.1 Preserving Symmetry 262
9.2.2 Efficient Implementations 265
9.3 Preconditioned Generalized Minimal Residual 267
9.3.1 Left-Preconditioned G1RES.268
9.3.2 Right-Preconditioned GMRES 269
9.3.3 Split Preconditioning 270
9.3.4 Comparison of Right and Left Preconditioning 271
9.4 Flexible Variants 272
9.4.1 FGMRES 273
9.4.2 DQGMRES 276
9.5 Preconditioned Conjugate Gradient for the Normal Equations 276
9.6 The Concus, Gol， and Widlund Algorithm 278
Exercises 279
Notes and References 280
10 Preconditioning Techniques 283
10.1 Introduction 283
10.2 Jacobi, Successive Overrelaxation, and Symmetric Successive Overrelaxation Preconditioners 284
10.3 Incomplete LU Factorization Preconditioners 287
10.3.1 ILU Factorizations 288
10.3.2 Zero Fill-in ILU (ILU(O)) 293
10.3.3 Level of Fill and ILU(p) 296
10.3.4 Matrices with Regular Structure 300
10.3.5 LU 305
10.4 Threshold Strategies and Incomplete LU with Threshold 306
10.4.1 The ILUT Approach 307
10.4.2 Analysis 308
10.4.3 Implmntation Details 310
10.4.4 ThILUTP Approach 312
10.4.5 The ILUS Approach 314
10.4.6 The ILUC Approach 316
10.5 Approximate Inverse Preconditioners 320
10.5.1 Approximating e Inverse of a Sparse Matrix 321
10.5.2 Globallteration 321
10.5.3 Column-OrientedAlgorithms 323
10.5.4 Theoretical Considerations 324
10.5.5 Convergence of Self-Preconditioned MR 326
10.5.6 AINVs via Bordering 329
10.5.7 Factor，d Invrses via Orthogonalization: AINV 331
10.5.8 Improving a Preconditioner 333
10.6 Reordering for Incomplete LU 333
10.6.1 Symmetric Permutations 333
10.6.2 Nonsymmetric Reorderings 335
10.7 Block Preconditioners 337
10.7.1 Block Tridiagonal Matrices 337
10.7.2 General Matrices 339
10.8 Preconditioners for thNormal Equations 339
10.8.1 Jacobi, SOR, and Variants 340
10.8.2 IC(O) for the Normal Equations 340
10.8.3 IncompletGram-Schmidt and ILQ 342
Exercises 345
Notes and Refernces 349
11 Parallel Implementations 353
11.1 Introduction 353
11.2 Forms of Parallelism 354
11.2.1 Multiple Functional Units 354
11.2.2 Pipelining 354
11.2.3 Vector Processors 355
11.2.4 Multiprocessing and Distributd Computing 355
11.3 Types of Parallel Architectures 355
11.3.1 Shared Memory Computers 356
11.3.2 Distributed Memory Architcturω 357
11.4 Types of Oprations 359
11.5 Matrix-by-Vector Products 361
11.5.1 The CSR and CSC Formats 362
11.5.2 Matvcs in thDiagonal Format 364
11.5.3 The Ellpack-Itpack Format 364
11.5.4 The JAD Format 365
11.5.5 The Case ofDistributed Sparse Matrices 366
11.6 Standard Preconditioning Oprations 369
11.6.1 Parallelism in Forward Sweeps 369
11.6.2 Level Scheduling: The CasofFive-Point Matrices 370
11.6.3 Level Scheduling for Irregular Graphs 370
Exerciss 373
Notes and References 375
12 Parallel Preconditioners 377
12.1 lntroduction 377
12.2 Block Jacobi Preconditioners 378
12.3 Polynomial Prconditioners 379
12.3.1 Numann Polynomials 380
12.3.2 Chebyshv Polynomials 381
12.3.3 Least-Squares Polynomials 383
12.3.4 The Nonsymmetric Case 386
12.4 Multicoloring 389
12.4.1 Red-Black Ordering 389
12.4.2 Solution of Rd-Black Systems 390
12.4.3 Multicoloring for General Sparse Matrices 391
12.5 Multi-Elimination Incomplete LU 392
12.5.1 Multi-Elimination 393
12.5.2 ILUM.….394
12.6 Distributed Incomplete LU and Symmetric Successive
Overrelaxation 396
12.7 Other Techniques 399
12.7.1 AINVs 399
12.7.2 EBE Techniques 399
12.7.3 Parallel Row Pr嚀ection Preconditioners 401
Exercises 402
Notes and References 404
13 Multigrid Methods 407
13.1 Introduction 407
13.2 Matrices and Spectra of Model Problems 408
13.2.1 The Richardson Iteration 412
13.2.2 Weighted Jacobi Iteration 414
13.2.3 Gauss-Seidel Itration 416
13.3 Intergrid Operations 419
13.3.1 Prolongation 419
13.3.2 Restriction 421
13.4 Standard Multigrid Techniques 422
13.4.1 Coarse Problems and Smoothers 423
13.4.2 Two-Grid Cycles 424
13.4.3 V-Cycles and W-Cycles 426
13.4.4 FMG 429
l3.5 Analysis of the Two-Grid Cycle 433
13.5.1 Two Important Subspaces 433
13.5.2 ConvergencεAnalysis 435
l3.6 Algebraic Multigrid 437
13.6.1 Smoothness in AMG 438
13.6.2 Interpolation in AMG 439
13.6.3 Defining Coarse Spaces in AMG 442
13.6.4 AMG via Multilevel ILU 442
13.7 Multigrid versus Krylov Methods 445
ExerCìses 446
Notes and Rferences 449
14 Domain Decomposition Methods 451
14.1 Introduction 451
14. 1.1 Notation 452
14. 1.2 Types ofPartitionings.453
14. 1.3 Types ofTechniques 453
14.2 Direct Solution and the Schur Complement 456
14.2.1 Block Gaussian Elimination 456
14.2.2 Properties of 出e Schur Complemnt 457
14.2.3 Schur Complement for VIdx-Basd Partitionings 458
14.2.4 Schur Complement for Finite Element Partitionings 460
14.2.5 Schur Complement for the Model Problem 463
14.3 Schwarz Altemating Procedures 465
14.3.1 Multiplicative Schwarz Procedure 465
14.3.2 Multiplicative Schwarz Preconditioning 470
14.3.3 Additive Schwarz Procedure 472
14.3.4 Convergence 473
14.4 Schur Complement Approach 477
14.4.1 Induced Preconditioners 478
14.4.2 Probing. 480
14.4.3 Pre conditioning Vertex-Based Schur Complements 480
14.5 Full Matrix Methods 481
14.6 Graph Partitioning 483
14.6.1 Basic Definitions 484
14.6.2 Geometric Approach 484
14.6.3 Spectral Techniques 486
14.6.4 Graph Theory Techniques 487
Exerciss.491
Nots and Refernces.492
Bibliography 495
Index 517