Iterative Methods for Sparse Linear Systems

1 Iterative Methods for Sparse Linear Systems Yousef Saad 6. 15 12. 4 9 5. 11 14 8. 2 10 3. 13 7. 1. Copyright c 2000 by Yousef Saad. S ECOND EDITION WITH CORRECTIONS . JANUARY 3 RD , 2000.. PREFACE xiii Acknowledgments .. xiv Suggestions for Teaching .. xv 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 .. 9. Orthogonal Vectors and Subspaces .. 10. Canonical Forms of Matrices .. 15. Reduction to the Diagonal Form .. 15. The Jordan Canonical Form .. 16. The Schur Canonical Form .. 17. Application to Powers of Matrices .. 19. Normal and Hermitian Matrices .. 21. Normal Matrices .. 21. Hermitian Matrices .. 24. Nonnegative Matrices, M-Matrices .. 26. Positive-Definite Matrices .. 30. Projection Operators .. 33. Range and Null Space of a Projector .. 33. Matrix Representations .. 35. Orthogonal and Oblique Projectors .. 35. Properties of Orthogonal Projectors.

2 37. Basic Concepts in Linear Systems .. 38. Existence of a Solution .. 38. Perturbation Analysis .. 39. Exercises and Notes .. 41. 2 DISCRETIZATION OF PDES 44. Partial Differential Equations .. 44. Elliptic Operators .. 45. The Convection Diffusion Equation .. 47.. Finite Difference Methods .. 47. Basic Approximations .. 48. Difference Schemes for the Laplacean Operator .. 49. Finite Differences for 1-D Problems .. 51. Upwind Schemes .. 51. Finite Differences for 2-D Problems .. 54. The Finite Element Method .. 55. Mesh Generation and Refinement .. 61. Finite Volume Method .. 63. Exercises and Notes .. 66. 3 Sparse MATRICES 68. Introduction .. 68. Graph Representations .. 70. Graphs and Adjacency Graphs .. 70. Graphs of PDE Matrices .. 72. Permutations and Reorderings .. 72. Basic Concepts .. 72. Relations with the Adjacency Graph .. 75. Common Reorderings .. 75. Irreducibility .. 83. Storage Schemes .. 84. Basic Sparse Matrix Operations .. 87. Sparse Direct Solution Methods .

3 88. Test Problems .. 88. Exercises and Notes .. 91. 4 BASIC Iterative Methods 95. Jacobi, Gauss-Seidel, and SOR .. 95. Block Relaxation Schemes .. 98. Iteration Matrices and Preconditioning .. 102. Convergence .. 104. General Convergence Result .. 104. Regular Splittings .. 107. Diagonally Dominant Matrices .. 108. Symmetric Positive Definite Matrices .. 112. Property A and Consistent Orderings .. 112. Alternating Direction Methods .. 116. Exercises and Notes .. 119. 5 PROJECTION Methods 122. Basic Definitions and Algorithms .. 122. General Projection Methods .. 123. Matrix Representation .. 124. General Theory .. 126. Two Optimality Results .. 126.. Interpretation in Terms of Projectors .. 127. General Error Bound .. 129. One-Dimensional Projection Processes .. 131. Steepest Descent .. 132. Minimal Residual (MR) Iteration .. 134. Residual Norm Steepest Descent .. 136. Additive and Multiplicative Processes .. 136. Exercises and Notes .. 139. 6 KRYLOV SUBSPACE Methods PART I 144.

4 Introduction .. 144. Krylov Subspaces .. 145. Arnoldi's Method .. 147. The Basic Algorithm .. 147. Practical Implementations .. 149. Arnoldi's Method for Linear Systems (FOM) .. 152. Variation 1: Restarted FOM .. 154. Variation 2: IOM and DIOM .. 155. GMRES .. 158. The Basic GMRES Algorithm .. 158. The Householder Version .. 159. Practical Implementation Issues .. 161. Breakdown of GMRES .. 165. Relations between FOM and GMRES .. 165. Variation 1: Restarting .. 168. Variation 2: Truncated GMRES Versions .. 169. The Symmetric Lanczos Algorithm .. 174. The Algorithm .. 174. Relation with Orthogonal Polynomials .. 175. The Conjugate Gradient Algorithm .. 176. Derivation and Theory .. 176. Alternative Formulations .. 180. Eigenvalue Estimates from the CG Coefficients .. 181. The Conjugate Residual Method .. 183. GCR, ORTHOMIN, and ORTHODIR .. 183. The Faber-Manteuffel Theorem .. 186. Convergence Analysis .. 188. Real Chebyshev Polynomials .. 188. Complex Chebyshev Polynomials.

5 189. Convergence of the CG Algorithm .. 193. Convergence of GMRES .. 194. Block Krylov Methods .. 197. Exercises and Notes .. 202. 7 KRYLOV SUBSPACE Methods PART II 205. Lanczos Biorthogonalization .. 205.. The Algorithm .. 205. Practical Implementations .. 208. The Lanczos Algorithm for Linear Systems .. 210. The BCG and QMR Algorithms .. 210. The Biconjugate Gradient Algorithm .. 211. Quasi-Minimal Residual Algorithm .. 212. Transpose-Free Variants .. 214. Conjugate Gradient Squared .. 215. BICGSTAB .. 217. Transpose-Free QMR (TFQMR) .. 221. Exercises and Notes .. 227. 8 Methods RELATED TO THE NORMAL EQUATIONS 230. The Normal Equations .. 230. Row Projection Methods .. 232. Gauss-Seidel on the Normal Equations .. 232. Cimmino's Method .. 234. Conjugate Gradient and Normal Equations .. 237. CGNR .. 237. CGNE .. 238. Saddle-Point Problems .. 240. Exercises and Notes .. 243. 9 PRECONDITIONED ITERATIONS 245. Introduction .. 245. Preconditioned Conjugate Gradient .. 246. Preserving Symmetry.

6 246. Efficient Implementations .. 249. Preconditioned GMRES .. 251. Left-Preconditioned GMRES .. 251. Right-Preconditioned GMRES .. 253. Split Preconditioning .. 254. Comparison of Right and Left Preconditioning .. 255. Flexible Variants .. 256. Flexible GMRES .. 256. DQGMRES .. 259. Preconditioned CG for the Normal Equations .. 260. The CGW Algorithm .. 261. Exercises and Notes .. 263. 10 PRECONDITIONING TECHNIQUES 265. Introduction .. 265. Jacobi, SOR, and SSOR Preconditioners .. 266. ILU Factorization Preconditioners .. 269. Incomplete LU Factorizations .. 270. Zero Fill-in ILU (ILU(0)) .. 275.. Level of Fill and ILU( ) .. 278. Matrices with Regular Structure .. 281. Modified ILU (MILU) .. 286. Threshold Strategies and ILUT .. 287. The ILUT Approach .. 288. Analysis .. 289. Implementation Details .. 292. The ILUTP Approach .. 294. The ILUS Approach .. 296. Approximate Inverse Preconditioners .. 298. Approximating the Inverse of a Sparse Matrix .. 299. Global Iteration.

7 299. Column-Oriented Algorithms .. 301. Theoretical Considerations .. 303. Convergence of Self Preconditioned MR .. 305. Factored Approximate Inverses .. 307. Improving a Preconditioner .. 310. Block Preconditioners .. 310. Block-Tridiagonal Matrices .. 311. General Matrices .. 312. Preconditioners for the Normal Equations .. 313. Jacobi, SOR, and Variants .. 313. IC(0) for the Normal Equations .. 314. Incomplete Gram-Schmidt and ILQ .. 316. Exercises and Notes .. 319. 11 PARALLEL IMPLEMENTATIONS 324. Introduction .. 324. Forms of Parallelism .. 325. Multiple Functional Units .. 325. Pipelining .. 326. Vector Processors .. 326. Multiprocessing and Distributed Computing .. 326. Types of Parallel Architectures .. 327. Shared Memory Computers .. 327. Distributed Memory Architectures .. 329. Types of Operations .. 331. Preconditioned CG .. 332. GMRES .. 332. Vector Operations .. 333. Reverse Communication .. 334. Matrix-by-Vector Products .. 335. The Case of Dense Matrices .. 335.

8 The CSR and CSC Formats .. 336. Matvecs in the Diagonal Format .. 339. The Ellpack-Itpack Format .. 340.. The Jagged Diagonal Format .. 341. The Case of Distributed Sparse Matrices .. 342. Standard Preconditioning Operations .. 345. Parallelism in Forward Sweeps .. 346. Level Scheduling: the Case of 5-Point Matrices .. 346. Level Scheduling for Irregular Graphs .. 347. Exercises and Notes .. 350. 12 PARALLEL PRECONDITIONERS 353. Introduction .. 353. Block-Jacobi Preconditioners .. 354. Polynomial Preconditioners .. 356. Neumann Polynomials .. 356. Chebyshev Polynomials .. 357. Least-Squares Polynomials .. 360. The Nonsymmetric Case .. 363. Multicoloring .. 365. Red-Black Ordering .. 366. Solution of Red-Black Systems .. 367. Multicoloring for General Sparse Matrices .. 368. Multi-Elimination ILU .. 369. Multi-Elimination .. 370. ILUM .. 371. Distributed ILU and SSOR .. 374. Distributed Sparse Matrices .. 374. Other Techniques .. 376. Approximate Inverses .. 377. Element-by-Element Techniques.

9 377. Parallel Row Projection Preconditioners .. 379. Exercises and Notes .. 380. 13 DOMAIN DECOMPOSITION Methods 383. Introduction .. 383. Notation .. 384. Types of Partitionings .. 385. Types of Techniques .. 386. Direct Solution and the Schur Complement .. 388. Block Gaussian Elimination .. 388. Properties of the Schur Complement .. 389. Schur Complement for Vertex-Based Partitionings .. 390. Schur Complement for Finite-Element Partitionings .. 393. Schwarz Alternating Procedures .. 395. Multiplicative Schwarz Procedure .. 395. Multiplicative Schwarz Preconditioning .. 400. Additive Schwarz Procedure .. 402. Convergence .. 404.. Schur Complement Approaches .. 408. Induced Preconditioners .. 408. Probing .. 410. Preconditioning Vertex-Based Schur Complements .. 411. Full Matrix Methods .. 412. Graph Partitioning .. 414. Basic Definitions .. 414. Geometric Approach .. 415. Spectral Techniques .. 417. Graph Theory Techniques .. 418. Exercises and Notes .. 422. REFERENCES 425.

10 INDEX 439. xii . Iterative Methods for solving general, large Sparse Linear Systems have been gaining popularity in many areas of scientific computing. Until recently, direct solution Methods were often preferred to Iterative Methods in real applications because of their robustness and predictable behavior. However, a number of efficient Iterative solvers were discovered and the increased need for solving very large Linear Systems triggered a noticeable and rapid shift toward Iterative techniques in many applications . This trend can be traced back to the 1960s and 1970s when two important develop- ments revolutionized solution Methods for large Linear Systems . First was the realization that one can take advantage of sparsity to design special direct Methods that can be quite economical. Initiated by electrical engineers, these direct Sparse solution Methods . led to the development of reliable and efficient general-purpose direct solution software codes over the next three decades.