Introductory Material. Vector and matrices norms.
Irreducibility and diagonal dominance.
M--Matrices and generalizations.
Positive definite matrices.
The graph of a matrix.
Discretization methods for partial diffential equations.
Eigenvalues and Fourier analysis.
Floating point arithmetic.
Vector and parallel computers.
BLAS and LAPACK.
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.
Gaussian elimination for symmetric systems.
The outer product algorithm.
The bordering algorithm.
The inner product algorithm.
Coding the three factorization algorithms.
Positive definite systems.
Gaussian elimination for H-matrices.
Tridiagonal and block tridiagonal systems.
Roundoff error analysis.
Parallel solution of general linear systems.
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.
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.
Fast solvers for separable PDEs.
Fast Fourier Transform.
The basics of the FFT.
The complex FFT.
The real transforms.
FFT on vector and parallel computers.
Stability of the FFT.
Double Fourier analysis.
The Fourier/tridiagonal Method.
The cyclic reduction method.
The FACR(l) method.
The capacitance matrix method.
Classical iterative methods.
The Jacobi method.
The Gauss-Seidel method.
The SOR Method.
The SSOR method.
Alternating direction methods.
Stability of classical iterative methods.
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.
The minimum residual method.
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.
Vector and parallel PCG.
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.
Truncated and restarted versions.
Methods equivalent to GMRES.
Methods equivalent to FOM.
Roundoff error analysis of GMRES.
Extensions to 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.
Modified Krylov spaces.
The Conjugate Gradient Squared algorithm.
Extensions of BiCG.
The Quasi Minimal Residual algorithm.
Which method to use?.
Complex linear systems.
Krylov methods on parallel computers.
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.
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.
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.
The block Cholesky decomposition for D problems.
D block preconditioners.
D point preconditioners.
D block preconditioners.
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.
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.
Element by element preconditioner.
Vector and parallel computing.
Vectorization of IC(,).
Vectorization of INV.
Twisted incomplete block factorizations.
Incomplete block cyclic reduction.
A massively parallel preconditioner.
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 coarse grid operator.
The multigrid method.
Complexity of multigrid.
The full multigrid method.
Vector and parallel multigrid.
Domain decomposition and multilevel methods.
Introduction to domain decomposition.
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.
Golub and Mayers' preconditioner.
The Neumann--Dirichlet preconditioner.
The Neumann--Neumann preconditioner.
Dependence on the aspect ratio.
Dependence on the coefficients.
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.
Additive multilevel Schwarz preconditioners.
Multilevel ILU preconditioners. Bibliographical comments.
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, Gauss-Seidel 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.
- No. of pages:
- © North Holland 1999
- 16th June 1999
- North Holland
- eBook ISBN:
- Hardcover ISBN: