Computer Solution of Large Linear Systems (eBook)

Front Cover 1
COMPUTER SOLUTION OF LARGE LINEAR SYSTEMS 4
Copyright Page 5
Preface 10
CONTENTS 12
Chapter 1. Introductory Material 24
1.1. Vector and matrices norms 25
1.2. Eigenvalues 32
1.3. Irreducibility and diagonal dominance 40
1.4. M–Matrices and generalizations 46
1.5. Splittings 52
1.6. Positive definite matrices 53
1.7. The graph of a matrix 58
1.8. Chebyshev polynomials 61
1 9 Discretization methods for partial differential equations 64
1.10. Eigenvalues and Fourier analysis 73
1.11. Floating point arithmetic 81
1.12. Vector and parallel computers 85
1.13. BLAS and LAPACK 88
1.14. Bibliographical comments 90
Chapter 2. Gaussian elimination for general linear systems 92
2.1. Introduction to Gaussian elimination 92
2.2. Gaussian elimination for symmetric systems 105
2.3. Gaussian elimination for H-matrices 118
2.4. Block methods 122
2.5. Tridiagonal and block tridiagonal systems 122
2.6. Roundoff error analysis 134
2.7. Perturbation analysis 140
2.8. Scaling 144
2.9. Iterative refinement 145
2.10. Parallel solution of general linear systems 146
2.11. Bibliographical comments 151
Chapter 3. Gaussian elimination for sparse linear systems 154
3.1. Introduction 154
3.2. The fill-in phenomenon 155
3.3. Graphs and fill-in for symmetric matrices 157
3.4. Characterization of the fill-in 160
3.5. Band and envelope numbering schemes for symmetric matrices 163
3.6. Spectral schemes 171
3.7. The minimum degree ordering 175
3.8. The nested dissection ordering 178
3.9. Generalization of dissection algorithms 182
3.10. The multifrontal method 186
3.11. Non-symmetric sparse matrices 189
3.12. Numerical stability for sparse matrices 192
3.13. Parallel algorithms for sparse matrices 193
3.14. Bibliographical comments 199
Chapter 4. Fast solvers for separable PDEs 200
4.1. Introduction 200
4.2. Fast Fourier Transform 202
4.3. The Fourier/tridiagonal Method 210
4.4. The cyclic reduction method 214
4.5. The FACR(1) method 225
4.6. The capacitance matrix method 226
4.7. Bibliographical comments 229
Chapter 5. Classical iterative methods 232
5.1. Introduction 232
5.2. The Jacobi method 233
5.3. The Gauss-Seidel method 241
5.4. The SOR Method 246
5.5. The SSOR method 252
5.6. Alternating direction methods 256
5.7. Richardson methods 264
5.8. Acceleration techniques 269
5.9. Stability of classical iterative methods 271
5.10. Bibliographical comments 273
Chapter 6. The conjugate gradient and related methods 274
6.1. Derivation of the method 274
6.2. Generalization and second form of PCG 279
6.3. Optimality of PCG 283
6.4. The convergence rate of PCG 288
6.5. The Lanczos algorithm 304
6.6. A posteriori error bounds 307
6.7. The Eisenstat's trick 325
6.8. The Conjugate Residual method 326
6.9. SYMMLQ 327
6.10. The minimum residual method 330
6.11. Hybrid algorithms 331
6.12. Roundoff errors of CG and Lanczos 333
6.13. Solving for several right hand sides 338
6.14. Block CG and Lanczos 342
6.15. Inner and outer iterations 346
6.16. Constrained CG 347
6.17. Vector and parallel PCG 348
6.18. Bibliographical comments 352
Chapter 7. Krylov methods for non–symmetric systems 354
7.1. The normal equations 355
7.2. The Concus and Golub non–symmetric CG 358
7.3. Construction of basis for Krylov spaces 360
7.4. FOM and GMRES 365
7.5. Roundoff error analysis of GMRES 380
7.6. Extensions to GMRES 383
7.7. Hybrid GMRES algorithms 386
7.8. The non–symmetric Lanczos algorithm 387
7.9. The BiConjugate Gradient Algorithm 393
7.10. Roundoff error analysis of BiCG 396
7.11. Handling of breakdowns 397
7.12. The Conjugate Gradient Squared algorithm 402
7.13. Extensions of BiCG 405
7.14. The Quasi Minimal Residual algorithm 410
7.15. CMRH 413
7.16. Which method to use? 414
7.17. Complex linear systems 415
7.18. Krylov methods on parallel computers 417
7.19. Bibliographical comments 417
Chapter 8. Preconditioning 420
8.1. Introduction 420
8.2. The diagonal preconditioner 422
8.3. The SSOR preconditioner 424
8.4. The block SSOR preconditioner 430
8.5. The incomplete Cholesky decomposition 439
8.6. The modified incomplete Cholesky decomposition 465
8.7. The relaxed incomplete Cholesky decomposition 471
8.8. More on the incomplete decompositions for the model problem 472
8.9. Stability of incomplete decomposition 475
8.10. The generalized SSOR preconditioner 477
8.11. Incomplete decomposition of positive definite matrices 481
8.12. Different orderings for IC 484
8.13. The repeated Red–Black decomposition 495
8.14. The block incomplete Cholesky decomposition 502
8.15. The block Cholesky decomposition for 3D problems 517
8.16. Nested factorization 524
8.17. Sparse approximate inverses 527
8.18. Polynomial preconditioners 532
8.19. Double preconditioners 551
8.20. Other ideas 552
8.21. Vector and parallel computing 555
8.22. Bibliographical comments 562
Chapter 9. Multigrid methods 564
9.1. Introduction 564
9.2. The two–grid method 565
9.3. A one dimensional example 569
9.4. The choices of components 580
9.5. The multigrid method 586
9.6. Convergence theory 590
9.7. Complexity of multigrid 594
9.8. The full multigrid method 596
9.9. Vector and parallel multigrid 599
9.10. Algebraic multigrid 602
9.11. Bibliographical comments 606
Chapter 10. Domain decomposition and multilevel methods 608
10.1. Introduction to domain decomposition 608
10.2. Schwarz methods 610
10.3. An additive Schwarz preconditioner for parabolic problems 620
10.4. Algebraic domain decomposition methods without overlapping 623
10.5. Approximate Schur complements in the two subdomains case 629
10.6. Approximations of Schur complements with many subdomains 650
10.7. Inexact subdomain solvers 655
10.8. Domain decomposition with boxes 660
10.9. A block Red–Black DD preconditioner 666
10.10. Multilevel preconditioners 669
10.11. Bibliographical comments 678
References 680
Index 772