Computer Solution of Large Linear Systems

Introductory Material. Vector and matrices norms. Eigenvalues. Irreducibility and diagonal dominance. M--Matrices and generalizations. Splittings. Positive definite matrices. The graph of a matrix. Chebyshev polynomials Discretization methods for partial diffential equations. Eigenvalues and Fourier analysis. Floating point arithmetic. Vector and parallel computers. BLAS and LAPACK. Bibliographical comments. Gaussian elimination for general linear systems. Introduction to Gaussian elimination. Gaussian elimination without permutations. Gaussian elimination with permutations (partial piv- oting). Gaussian elimination with other pivoting strategies. Operation counts. Gaussian elimination for symmetric systems. The outer product algorithm. The bordering algorithm. The inner product algorithm. Coding the three factorization algorithms. Positive definite systems. Indefinite systems. Gaussian elimination for H-matrices. Block methods. Tridiagonal and block tridiagonal systems. Roundoff error analysis. Perturbation analysis. Scaling. Iterative refinement. Parallel solution of general linear systems. Bibliographical comments. Gaussian elimination for sparse linear systems. Introduction. The fill--in phenomenon. Graphs and fill--in for symmetric matrices. Characterization of the fill--in. Band and envelope numbering schemes for symmetric matrices. The Cuthill--McKee and reverse Cuthill--McKee orderings. Sloan's algorithm. Spectral schemes. The basic idea. The multilevel spectral algorithm. The Kumfert and Pothen hybrid algorithm. The Boman--Hendrickson multilevel algorithm. The minimum degree ordering. The nested dissection ordering. Generalization of dissection algorithms. General dissection algorithms. Graph bisection improvement techniques. The multisection algorithm. The multifrontal method. Non--symmetric sparse matrices. Numerical stability for sparse matrices. Parallel algorithms for sparse matrices. Bibliographical comments. Fast solvers for separable PDEs. Introduction. Fast Fourier Transform. The basics of the FFT. The complex FFT. The real transforms. FFT on vector and parallel computers. Stability of the FFT. Other algorithms. Double Fourier analysis. The Fourier/tridiagonal Method. The cyclic reduction method. The FACR(l) method. The capacitance matrix method. Bibliographical comments. Classical iterative methods. Introduction. The Jacobi method. The Gauss-Seidel method. The SOR Method. The SSOR method. Alternating direction methods. Richardson methods. Acceleration techniques. Stability of classical iterative methods. Bibliographical comments. The conjugate gradient and related methods. Derivation of the method. Generalization and second form of PCG. Optimality of PCG. The convergence rate of PCG. The Lanczos algorithm. A posteriori error bounds. The Eisenstat's trick. The Conjugate Residual method. SYMMLQ. The minimum residual method. Hybrid algorithms. Roundoff errors of CG and Lanczos. Solving for several right hand sides. Block CG and Lanczos. The block Lanczos algorithm. The Block CG algorithm. Inner and outer iterations. Constrained CG. Vector and parallel PCG. Bibliographical comments. Krylov methods for non--symmetric systems. The normal equations. The Concus and Golub non--symmetric CG. Construction of basis for Krylov spaces. The Arnoldi algorithm. The Hessenberg algorithm. The generalized Hessenberg process. FOM and GMRES. Definition of FOM and GMRES. Convergence results. Truncated and restarted versions. Methods equivalent to GMRES. Methods equivalent to FOM. Roundoff error analysis of GMRES. Extensions to GMRES. Flexible GMRES. GMRES*. Hybrid GMRES algorithms. The non--symmetric Lanczos algorithm. Definition of the non--symmetric Lanczos algorithm. Variants of the non--symmetric Lanczos algorithm. Maintaining semi bi--orthogonality. The BiConjugate Gradient Algorithm. Roundo# error analysis of BiCG. Handling of breakdowns. FOP. Pad'e approximation. Block bi--orthogonality. Modified Krylov spaces. The Conjugate Gradient Squared algorithm. Extensions of BiCG. The Quasi Minimal Residual algorithm. CMRH. Which method to use?. Complex linear systems. Krylov methods on parallel computers. Bibliographical comments. Preconditioning. Introduction. The diagonal preconditioner. The SSOR preconditioner. Definition of SSOR. Convergence results for SSOR. Fourier analysis of SSOR. The block SSOR preconditioner. Definition of BSSOR. Analysis of BSSOR. Fourier analysis of BSSOR. The incomplete Cholesky decomposition. The general decomposition. Incomplete decomposition of H--matrices. Incomplete decomposition of non--symmetric matrices. Different incomplete decomposition strategies. Finite difference matrices. Fourier analysis of IC(,). Comparison of periodic and Dirichlet boundary condi- tions. Axelsson's results. The modified incomplete Cholesky decomposition. The DKR preconditioner. Analysis of DKR. Fourier analysis of DKR. Extensions of DKR. The relaxed incomplete Cholesky decomposition. More on the incomplete decompositions for the model problem. Stability of incomplete decomposition. The generalized SSOR preconditioner. Incomplete decomposition of positive definite matrices. Di#erent orderings for IC. Experimental results. Theory for model problems. Value dependent orderings. Multicolor orderings. The repeated Red--Black decomposition. Description of the methods. Analysis of RRB. The block incomplete Cholesky decomposition. Block tridiagonal matrices. Pointwise equivalent decomposition. The modified incomplete block decomposition. Block incomplete decomposition for H--matrices. Generalization of the block incomplete decomposition. Fourier analysis of INV and MINV. Axelsson's results. Block--size reduction. The block Cholesky decomposition for D problems. Point preconditioners. D block preconditioners. D point preconditioners. D block preconditioners. Nested factorization. The ACP preconditioner for D problems. The preconditioner of Appleyard, Cheshire and Pol- lard. Improvements of ACP. Sparse approximate inverses. The sparse inverses of Huckle and Grote. The sparse inverses of Gould and Scott. The sparse inverses of Chow and Saad. Sparse approximate inverses for symmetric matrices. The sparse inverses of Benzi, Meyer and Tuma. Polynomial preconditioners. Truncated Neumann series. The minmax polynomial. Least squares polynomials. Stable evaluation of polynomials. A polynomial independent of eigenvalue estimates. Adaptive algorithms for SPD matrices. Polynomials for symmetric indefinite problems. Polynomials for non--symmetric problems. Double preconditioners. Other ideas. ADI preconditioner. ADDKR preconditioner. Element by element preconditioner. Fast solvers. Wavelets. Vector and parallel computing. Vectorization of IC(,). Parallel orderings. Vectorization of INV. Twisted incomplete block factorizations. Incomplete block cyclic reduction. A massively parallel preconditioner. Bibliographical comments. Multigrid methods. Introduction. The two--grid method. A one dimensional example. The choice of the smoothing. The choice of the restriction. The choice of prolongation. The choice of the coarse grid matrix. The choices of components. The smoothing. The coarsening. Grid transfers. The coarse grid operator. The multigrid method. Convergence theory. Complexity of multigrid. The full multigrid method. Vector and parallel multigrid. Algebraic multigrid. Bibliographical comments. Domain decomposition and multilevel methods. Introduction to domain decomposition. Schwarz methods. The classical Schwarz alternating method. The matrix form of the Schwarz alternating method. The rate of convergence. Other boundary conditions. Parallelizing multiplicative Schwarz. The additive Schwarz method. Adding a coarse mesh correction. An additive Schwarz preconditioner for parabolic problems. Algebraic domain decomposition methods without overlapping. Exact solvers for the subdomains. Approximate solvers for the subdomains. Approximate Schur complements in the two subdomains case. The Schur complement for block tridiagonal matrices. Eigenvalues of the Schur complement for separable problems. Dryja's preconditioner. Golub and Mayers' preconditioner. The Neumann--Dirichlet preconditioner. The Neumann--Neumann preconditioner. Dependence on the aspect ratio. Dependence on the coefficients. Probing. INV and MINV approximations. The Schur complement for more general problems. Approximations of Schur complements with many subdomains. Inexact subdomain solvers. Domain decomposition with boxes. The Bramble, Pasciak and Schatz preconditioner. Vertex space preconditioners. A block Red--Black DD preconditioner. Multilevel preconditioners. Additive multilevel Schwarz preconditioners. Multilevel ILU preconditioners. Bibliographical comments. References. Index.