COMPUTER SOLUTION OF LARGE LINEAR SYSTEMSSTUDIES IN MATHEMATICS AND ITS APPLICATIONS VOLUME 28 (SMIA)
This book deals with numerical methods for solving large sparse linear systems of equations, particularly those arising from the discretization of partial differential equations. It covers both direct and iterative methods. Direct methods which are considered are variants of Gaussian elimination and fast solvers for separable partial differential equations in rectangular domains. The book reviews the classical iterative methods like Jacobi, GaussSeidel and alternating directions algorithms. A particular emphasis is put on the conjugate gradient as well as conjugate gradient like methods for non symmetric problems. Most efficient preconditioners used to speed up convergence are studied. A chapter is devoted to the multigrid method and the book ends with domain decomposition algorithms that are well suited for solving linear systems on parallel computers.
Studies in Mathematics and its Applications
,
Published: June 1999
Imprint: Northholland
ISBN: 9780444501691
Reviews

...This book covers most of the best algorithms known so far for solving sparse linear systems of equations. It should be useful for engineers and scientists as well as graduate students interested in numerical computations....The book is very well written and can be used by mathematicians, engineers as well as by g students interested in numerical computation. I consider the book a marvelous introduction in the computer solution of large linear systems. T should be congratulated for his excellent work. I enthusiastically recommend the book.
Dr. Marius Radulescu, The Electronic International Journal Advanced Modeling and Optimization, December 1999
...will certainly become the standard book for linear system solvers.
U. Langer, Zentralblatt fur Mathematik, 2000
...this book gives the reader a good idea of what is in the arsenal for solving large sparse linear systems. This reviewer expects to refer to it often.
J.L. Barlow, Mathematical Reviews, 2000
Contents
 Introductory Material. Vector and matrices norms. Eigenvalues. Irreducibility and diagonal dominance. MMatrices 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 Hmatrices. 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 fillin phenomenon. Graphs and fillin for symmetric matrices. Characterization of the fillin. Band and envelope numbering schemes for symmetric matrices. The CuthillMcKee and reverse CuthillMcKee orderings. Sloan's algorithm. Spectral schemes. The basic idea. The multilevel spectral algorithm. The Kumfert and Pothen hybrid algorithm. The BomanHendrickson 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. Nonsymmetric 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 GaussSeidel 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 nonsymmetric systems. The normal equations. The Concus and Golub nonsymmetric 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 nonsymmetric Lanczos algorithm. Definition of the nonsymmetric Lanczos algorithm. Variants of the nonsymmetric Lanczos algorithm. Maintaining semi biorthogonality. The BiConjugate Gradient Algorithm. Roundo# error analysis of BiCG. Handling of breakdowns. FOP. Pad'e approximation. Block biorthogonality. 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 Hmatrices. Incomplete decomposition of nonsymmetric 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 RedBlack 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 Hmatrices. Generalization of the block incomplete decomposition. Fourier analysis of INV and MINV. Axelsson's results. Blocksize 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 nonsymmetric 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 twogrid 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 NeumannDirichlet preconditioner. The NeumannNeumann 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 RedBlack DD preconditioner. Multilevel preconditioners. Additive multilevel Schwarz preconditioners. Multilevel ILU preconditioners. Bibliographical comments. References. Index.