Iterative Methods for Sparse Linear Systems Second Edition

1 Iterative Methods for Sparse Linear Systems Second Edition +07. Yousef Saad Copyright 2003. c by the Society for Industrial and Applied Mathematics Contents Preface xiii Preface to. Second .. Edition .. xiii Preface to. first .. Edition .. xix 1 Background in Linear Algebra 1. Matrices .. 1. Square Matrices and Eigenvalues .. 3. Types of Matrices .. 4. Vector Inner Products and Norms .. 6. Matrix Norms .. 8. Subspaces, Range, and Kernel .. 10. Orthogonal Vectors and Subspaces .. 11. Canonical Forms of Matrices .. 15. Reduction to the Diagonal Form .. 16. The Jordan Canonical Form.

2 17. The Schur Canonical Form .. 17. Application to Powers of Matrices .. 20. Normal and Hermitian Matrices .. 21. Normal Matrices .. 21. Hermitian Matrices .. 25. Nonnegative Matrices, M-Matrices .. 27. Positive-Definite Matrices .. 32. Projection Operators .. 34. Range and Null Space of a Projector .. 34. Matrix Representations .. 36. Orthogonal and Oblique Projectors .. 37. Properties of Orthogonal Projectors .. 38. Basic Concepts in Linear Systems .. 39. Existence of a Solution .. 40. Perturbation Analysis .. 41. 2 Discretization of PDEs 47. Partial Differential Equations .. 47.

3 Elliptic Operators .. 47. v vi CONTENTS. The Convection Diffusion Equation .. 50. Finite Difference Methods .. 50. Basic Approximations .. 50. Difference Schemes for the Laplacean Operator . 52. Finite Differences for 1-D Problems .. 53. Upwind Schemes .. 54. Finite Differences for 2-D Problems .. 56. Fast Poisson Solvers .. 58. The Finite Element Method .. 62. Mesh Generation and Refinement .. 69. Finite Volume Method .. 69. 3 Sparse Matrices 75. Introduction .. 75. Graph Representations .. 76. Graphs and Adjacency Graphs .. 77. Graphs of PDE Matrices .. 78. Permutations and Reorderings.

4 79. Basic Concepts .. 79. Relations with the Adjacency Graph .. 81. Common Reorderings .. 83. Irreducibility .. 91. Storage Schemes .. 92. Basic Sparse Matrix Operations .. 95. Sparse Direct Solution Methods .. 96. Minimum degree ordering .. 97. Nested Dissection ordering .. 97. Test Problems .. 98. 4 Basic Iterative Methods 105. Jacobi, Gauss-Seidel, and SOR .. 105. Block Relaxation Schemes .. 108. Iteration Matrices and Preconditioning .. 112. Convergence .. 114. General Convergence Result .. 115. Regular Splittings .. 118. Diagonally Dominant Matrices .. 119. Symmetric Positive Definite Matrices.

5 122. Property A and Consistent Orderings .. 123. Alternating Direction Methods .. 127. 5 Projection Methods 133. Basic Definitions and Algorithms .. 133. General Projection Methods .. 134. CONTENTS vii Matrix Representation .. 135. General Theory .. 137. Two Optimality Results .. 137. Interpretation in Terms of Projectors .. 138. General Error Bound .. 140. One-Dimensional Projection Processes .. 142. Steepest Descent .. 142. Minimal Residual (MR) Iteration .. 145. Residual Norm Steepest Descent .. 147. Additive and Multiplicative Processes .. 147. 6 Krylov Subspace Methods Part I 157.

6 Introduction .. 157. Krylov Subspaces .. 158. Arnoldi's Method .. 160. The Basic Algorithm .. 160. Practical Implementations .. 162. Arnoldi's Method for Linear Systems (FOM) .. 165. Variation 1: Restarted FOM .. 167. Variation 2: IOM and DIOM .. 168. GMRES .. 171. The Basic GMRES Algorithm .. 172. The Householder Version .. 173. Practical Implementation Issues .. 174. Breakdown of GMRES .. 179. Variation 1: Restarting .. 179. Variation 2: Truncated GMRES Versions .. 180. Relations between FOM and GMRES .. 185. Residual smoothing .. 190. GMRES for complex Systems .. 193. The Symmetric Lanczos Algorithm.

7 194. The Algorithm .. 194. Relation with Orthogonal Polynomials .. 195. The Conjugate Gradient Algorithm .. 196. Derivation and Theory .. 196. Alternative Formulations .. 200. Eigenvalue Estimates from the CG Coefficients .. 201. The Conjugate Residual Method .. 203. GCR, ORTHOMIN, and ORTHODIR .. 204. The Faber-Manteuffel Theorem .. 206. Convergence Analysis .. 208. Real Chebyshev Polynomials .. 209. Complex Chebyshev Polynomials .. 210. Convergence of the CG Algorithm .. 214. viii CONTENTS. Convergence of GMRES .. 215. Block Krylov Methods .. 218. 7 Krylov Subspace Methods Part II 229.

8 Lanczos Biorthogonalization .. 229. The Algorithm .. 229. Practical Implementations .. 232. The Lanczos Algorithm for Linear Systems .. 234. The BCG and QMR Algorithms .. 234. The Biconjugate Gradient Algorithm .. 234. Quasi-Minimal Residual Algorithm .. 236. Transpose-Free Variants .. 241. Conjugate Gradient Squared .. 241. BICGSTAB .. 244. Transpose-Free QMR (TFQMR) .. 247. 8 Methods Related to the Normal Equations 259. The Normal Equations .. 259. Row Projection Methods .. 261. Gauss-Seidel on the Normal Equations .. 261. Cimmino's Method .. 263. Conjugate Gradient and Normal Equations.

9 266. CGNR .. 266. CGNE .. 267. Saddle-Point Problems .. 268. 9 Preconditioned Iterations 275. Introduction .. 275. Preconditioned Conjugate Gradient .. 276. Preserving Symmetry .. 276. Efficient Implementations .. 279. Preconditioned GMRES .. 282. Left-Preconditioned GMRES .. 282. Right-Preconditioned GMRES .. 284. Split Preconditioning .. 285. Comparison of Right and Left Preconditioning .. 285. Flexible Variants .. 287. Flexible GMRES .. 287. DQGMRES .. 290. Preconditioned CG for the Normal Equations .. 291. The Concus, Golub, and Widlund Algorithm .. 292. 10 Preconditioning Techniques 297.

10 Introduction .. 297. Jacobi, SOR, and SSOR Preconditioners .. 298. CONTENTS ix ILU Factorization Preconditioners .. 301. Incomplete LU Factorizations .. 301. Zero Fill-in ILU (ILU(0)) .. 307. Level of Fill and ILU(p) .. 311. Matrices with Regular Structure .. 315. Modified ILU (MILU) .. 319. Threshold Strategies and ILUT .. 321. The ILUT Approach .. 321. Analysis .. 323. Implementation Details .. 325. The ILUTP Approach .. 327. The ILUS Approach .. 330. The Crout ILU Approach .. 332. Approximate Inverse Preconditioners .. 336. Approximating the Inverse of a Sparse Matrix .. 337. Global Iteration.