Iterative Methods
for Sparse
Linear Systems
Yousef Saad
1
2 3
4 5
6
7
8
9
10
11
12
13
14
15
Copyright
c
2000 by Yousef Saad.
SECOND EDITION WITH CORRECTIONS. JANUARY 3RD, 2000.
PREFACE xiii
Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiv
Suggestions for Teaching . . . . . . . . . . . . . . . . . . . . . . . . . xv
1 BACKGROUND IN LINEAR ALGEBRA 1
1.1 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Square Matrices and Eigenvalues . . . . . . . . . . . . . . . . . . . . . 3
1.3 Types of Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Vector Inner Products and Norms . . . . . . . . . . . . . . . . . . . . . 6
1.5 Matrix Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.6 Subspaces, Range, and Kernel . . . . . . . . . . . . . . . . . . . . . . . 9
1.7 Orthogonal Vectors and Subspaces . . . . . . . . . . . . . . . . . . . . 10
1.8 Canonical Forms of Matrices . . . . . . . . . . . . . . . . . . . . . . . 15
1.8.1 Reduction to the Diagonal Form . . . . . . . . . . . . . . . . . 15
1.8.2 The Jordan Canonical Form . . . . . . . . . . . . . . . . . . . . 16
1.8.3 The Schur Canonical Form . . . . . . . . . . . . . . . . . . . . 17
1.8.4 Application to Powers of Matrices . . . . . . . . . . . . . . . . 19
1.9 Normal and Hermitian Matrices . . . . . . . . . . . . . . . . . . . . . . 21
1.9.1 Normal Matrices . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.9.2 Hermitian Matrices . . . . . . . . . . . . . . . . . . . . . . . . 24
1.10 Nonnegative Matrices, M-Matrices . . . . . . . . . . . . . . . . . . . . 26
1.11 Positive-Definite Matrices . . . . . . . . . . . . . . . . . . . . . . . . . 30
1.12 Projection Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
1.12.1 Range and Null Space of a Projector . . . . . . . . . . . . . . . 33
1.12.2 Matrix Representations . . . . . . . . . . . . . . . . . . . . . . 35
1.12.3 Orthogonal and Oblique Projectors . . . . . . . . . . . . . . . . 35
1.12.4 Properties of Orthogonal Projectors . . . . . . . . . . . . . . . . 37
1.13 Basic Concepts in Linear Systems . . . . . . . . . . . . . . . . . . . . . 38
1.13.1 Existence of a Solution . . . . . . . . . . . . . . . . . . . . . . 38
1.13.2 Perturbation Analysis . . . . . . . . . . . . . . . . . . . . . . . 39
Exercises and Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2 DISCRETIZATION OF PDES 44
2.1 Partial Differential Equations . . . . . . . . . . . . . . . . . . . . . . . 44
2.1.1 Elliptic Operators . . . . . . . . . . . . . . . . . . . . . . . . . 45
2.1.2 The Convection Diffusion Equation . . . . . . . . . . . . . . . 47
2.2 Finite Difference Methods . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.2.1 Basic Approximations . . . . . . . . . . . . . . . . . . . . . . . 48
2.2.2 Difference Schemes for the Laplacean Operator . . . . . . . . . 49
2.2.3 Finite Differences for 1-D Problems . . . . . . . . . . . . . . . 51
2.2.4 Upwind Schemes . . . . . . . . . . . . . . . . . . . . . . . . . 51
2.2.5 Finite Differences for 2-D Problems . . . . . . . . . . . . . . . 54
2.3 The Finite Element Method . . . . . . . . . . . . . . . . . . . . . . . . 55
2.4 Mesh Generation and Refinement . . . . . . . . . . . . . . . . . . . . . 61
2.5 Finite Volume Method . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
Exercises and Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3 SPARSE MATRICES 68
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
3.2 Graph Representations . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
3.2.1 Graphs and Adjacency Graphs . . . . . . . . . . . . . . . . . . 70
3.2.2 Graphs of PDE Matrices . . . . . . . . . . . . . . . . . . . . . 72
3.3 Permutations and Reorderings . . . . . . . . . . . . . . . . . . . . . . . 72
3.3.1 Basic Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . 72
3.3.2 Relations with the Adjacency Graph . . . . . . . . . . . . . . . 75
3.3.3 Common Reorderings . . . . . . . . . . . . . . . . . . . . . . . 75
3.3.4 Irreducibility . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
3.4 Storage Schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
3.5 Basic Sparse Matrix Operations . . . . . . . . . . . . . . . . . . . . . . 87
3.6 Sparse Direct Solution Methods . . . . . . . . . . . . . . . . . . . . . . 88
3.7 Test Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
Exercises and Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
4 BASIC ITERATIVE METHODS 95
4.1 Jacobi, Gauss-Seidel, and SOR . . . . . . . . . . . . . . . . . . . . . . 95
4.1.1 Block Relaxation Schemes . . . . . . . . . . . . . . . . . . . . 98
4.1.2 Iteration Matrices and Preconditioning . . . . . . . . . . . . . . 102
4.2 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
4.2.1 General Convergence Result . . . . . . . . . . . . . . . . . . . 104
4.2.2 Regular Splittings . . . . . . . . . . . . . . . . . . . . . . . . . 107
4.2.3 Diagonally Dominant Matrices . . . . . . . . . . . . . . . . . . 108
4.2.4 Symmetric Positive Definite Matrices . . . . . . . . . . . . . . 112
4.2.5 Property A and Consistent Orderings . . . . . . . . . . . . . . . 112
4.3 Alternating Direction Methods . . . . . . . . . . . . . . . . . . . . . . 116
Exercises and Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
5 PROJECTION METHODS 122
5.1 Basic Definitions and Algorithms . . . . . . . . . . . . . . . . . . . . . 122
5.1.1 General Projection Methods . . . . . . . . . . . . . . . . . . . 123
5.1.2 Matrix Representation . . . . . . . . . . . . . . . . . . . . . . . 124
5.2 General Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
5.2.1 Two Optimality Results . . . . . . . . . . . . . . . . . . . . . . 126
5.2.2 Interpretation in Terms of Projectors . . . . . . . . . . . . . . . 127
5.2.3 General Error Bound . . . . . . . . . . . . . . . . . . . . . . . 129
5.3 One-Dimensional Projection Processes . . . . . . . . . . . . . . . . . . 131
5.3.1 Steepest Descent . . . . . . . . . . . . . . . . . . . . . . . . . 132
5.3.2 Minimal Residual (MR) Iteration . . . . . . . . . . . . . . . . . 134
5.3.3 Residual Norm Steepest Descent . . . . . . . . . . . . . . . . . 136
5.4 Additive and Multiplicative Processes . . . . . . . . . . . . . . . . . . . 136
Exercises and Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
6 KRYLOV SUBSPACE METHODS – PART I 144
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
6.2 Krylov Subspaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
6.3 Arnoldi’s Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
6.3.1 The Basic Algorithm . . . . . . . . . . . . . . . . . . . . . . . 147
6.3.2 Practical Implementations . . . . . . . . . . . . . . . . . . . . . 149
6.4 Arnoldi’s Method for Linear Systems (FOM) . . . . . . . . . . . . . . . 152
6.4.1 Variation 1: Restarted FOM . . . . . . . . . . . . . . . . . . . . 154
6.4.2 Variation 2: IOM and DIOM . . . . . . . . . . . . . . . . . . . 155
6.5 GMRES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
6.5.1 The Basic GMRES Algorithm . . . . . . . . . . . . . . . . . . 158
6.5.2 The Householder Version . . . . . . . . . . . . . . . . . . . . . 159
6.5.3 Practical Implementation Issues . . . . . . . . . . . . . . . . . 161
6.5.4 Breakdown of GMRES . . . . . . . . . . . . . . . . . . . . . . 165
6.5.5 Relations between FOM and GMRES . . . . . . . . . . . . . . 165
6.5.6 Variation 1: Restarting . . . . . . . . . . . . . . . . . . . . . . 168
6.5.7 Variation 2: Truncated GMRES Versions . . . . . . . . . . . . . 169
6.6 The Symmetric Lanczos Algorithm . . . . . . . . . . . . . . . . . . . . 174
6.6.1 The Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
6.6.2 Relation with Orthogonal Polynomials . . . . . . . . . . . . . . 175
6.7 The Conjugate Gradient Algorithm . . . . . . . . . . . . . . . . . . . . 176
6.7.1 Derivation and Theory . . . . . . . . . . . . . . . . . . . . . . 176
6.7.2 Alternative Formulations . . . . . . . . . . . . . . . . . . . . . 180
6.7.3 Eigenvalue Estimates from the CG Coefficients . . . . . . . . . 181
6.8 The Conjugate Residual Method . . . . . . . . . . . . . . . . . . . . . 183
6.9 GCR, ORTHOMIN, and ORTHODIR . . . . . . . . . . . . . . . . . . . 183
6.10 The Faber-Manteuffel Theorem . . . . . . . . . . . . . . . . . . . . . . 186
6.11 Convergence Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
6.11.1 Real Chebyshev Polynomials . . . . . . . . . . . . . . . . . . . 188
6.11.2 Complex Chebyshev Polynomials . . . . . . . . . . . . . . . . 189
6.11.3 Convergence of the CG Algorithm . . . . . . . . . . . . . . . . 193
6.11.4 Convergence of GMRES . . . . . . . . . . . . . . . . . . . . . 194
6.12 Block Krylov Methods . . . . . . . . . . . . . . . . . . . . . . . . . . 197
Exercises and Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
7 KRYLOV SUBSPACE METHODS – PART II 205
7.1 Lanczos Biorthogonalization . . . . . . . . . . . . . . . . . . . . . . . 205
7.1.1 The Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
7.1.2 Practical Implementations . . . . . . . . . . . . . . . . . . . . . 208
7.2 The Lanczos Algorithm for Linear Systems . . . . . . . . . . . . . . . . 210
7.3 The BCG and QMR Algorithms . . . . . . . . . . . . . . . . . . . . . . 210
7.3.1 The Biconjugate Gradient Algorithm . . . . . . . . . . . . . . . 211
7.3.2 Quasi-Minimal Residual Algorithm . . . . . . . . . . . . . . . 212
7.4 Transpose-Free Variants . . . . . . . . . . . . . . . . . . . . . . . . . . 214
7.4.1 Conjugate Gradient Squared . . . . . . . . . . . . . . . . . . . 215
7.4.2 BICGSTAB . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
7.4.3 Transpose-Free QMR (TFQMR) . . . . . . . . . . . . . . . . . 221
Exercises and Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
8 METHODS RELATED TO THE NORMAL EQUATIONS 230
8.1 The Normal Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . 230
8.2 Row Projection Methods . . . . . . . . . . . . . . . . . . . . . . . . . 232
8.2.1 Gauss-Seidel on the Normal Equations . . . . . . . . . . . . . . 232
8.2.2 Cimmino’s Method . . . . . . . . . . . . . . . . . . . . . . . . 234
8.3 Conjugate Gradient and Normal Equations . . . . . . . . . . . . . . . . 237
8.3.1 CGNR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237
8.3.2 CGNE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
8.4 Saddle-Point Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 240
Exercises and Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
9 PRECONDITIONED ITERATIONS 245
9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
9.2 Preconditioned Conjugate Gradient . . . . . . . . . . . . . . . . . . . . 246
9.2.1 Preserving Symmetry . . . . . . . . . . . . . . . . . . . . . . . 246
9.2.2 Efficient Implementations . . . . . . . . . . . . . . . . . . . . . 249
9.3 Preconditioned GMRES . . . . . . . . . . . . . . . . . . . . . . . . . . 251
9.3.1 Left-Preconditioned GMRES . . . . . . . . . . . . . . . . . . . 251
9.3.2 Right-Preconditioned GMRES . . . . . . . . . . . . . . . . . . 253
9.3.3 Split Preconditioning . . . . . . . . . . . . . . . . . . . . . . . 254
9.3.4 Comparison of Right and Left Preconditioning . . . . . . . . . . 255
9.4 Flexible Variants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256
9.4.1 Flexible GMRES . . . . . . . . . . . . . . . . . . . . . . . . . 256
9.4.2 DQGMRES . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259
9.5 Preconditioned CG for the Normal Equations . . . . . . . . . . . . . . . 260
9.6 The CGW Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 261
Exercises and Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
10 PRECONDITIONING TECHNIQUES 265
10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
10.2 Jacobi, SOR, and SSOR Preconditioners . . . . . . . . . . . . . . . . . 266
10.3 ILU Factorization Preconditioners . . . . . . . . . . . . . . . . . . . . 269
10.3.1 Incomplete LU Factorizations . . . . . . . . . . . . . . . . . . . 270
10.3.2 Zero Fill-in ILU (ILU(0)) . . . . . . . . . . . . . . . . . . . . . 275
