内容

目次

Introductory Material. Vector and matrices norms. Eigenvalues.Irreducibility and diagonal dominance. M--Matricesand generalizations. Splittings. Positivedefinite matrices. The graph of a matrix.Chebyshev polynomials Discretization methods for partialdiffential equations. Eigenvalues and Fourier analysis.Floating point arithmetic. Vector and parallel computers.BLAS and LAPACK. Bibliographical comments.Gaussian elimination for general linear systems. Introduction toGaussian elimination. Gaussian elimination without permutations.Gaussian elimination with permutations (partial piv- oting).Gaussian elimination with other pivoting strategies. Operationcounts. Gaussian elimination for symmetric systems. Theouter product algorithm. The bordering algorithm. Theinner 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 erroranalysis. Perturbation analysis. Scaling.Iterative refinement. Parallel solution ofgeneral linear systems. Bibliographical comments.Gaussian elimination for sparse linear systems. Introduction. Thefill--in phenomenon. Graphs and fill--in for symmetric matrices.Characterization of the fill--in. Band and envelopenumbering schemes for symmetric matrices. The Cuthill--McKee and reverseCuthill--McKee orderings. Sloan's algorithm.Spectral schemes. The basic idea. Themultilevel spectral algorithm. The Kumfert and Pothen hybridalgorithm. The Boman--Hendrickson multilevel algorithm. The minimumdegree ordering. The nested dissection ordering.Generalization of dissection algorithms. General dissectionalgorithms. Graph bisection improvement techniques. Themultisection algorithm. The multifrontal method.Non--symmetric sparse matrices. Numerical stability for sparsematrices. Parallel algorithms for sparse matrices.Bibliographical comments. Fast solvers for separable PDEs.Introduction. Fast Fourier Transform.The basics of the FFT. The complex FFT. Thereal transforms. FFT on vector and parallel computers.Stability of the FFT. Other algorithms. DoubleFourier 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 iterativemethods. Bibliographical comments. The conjugategradient 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 severalright hand sides. Block CG and Lanczos. The blockLanczos algorithm. The Block CG algorithm. Inner andouter iterations. Constrained CG. Vector andparallel PCG. Bibliographical comments. Krylovmethods for non--symmetric systems. The normal equations.The Concus and Golub non--symmetric CG. Construction of basisfor Krylov spaces. The Arnoldi algorithm. TheHessenberg 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 GMRESalgorithms. The non--symmetric Lanczos algorithm. Definitionof the non--symmetric Lanczos algorithm. Variants of the non--symmetricLanczos algorithm. Maintaining semi bi--orthogonality. TheBiConjugate Gradient Algorithm. Roundo# error analysis of BiCG.Handling of breakdowns. FOP.Pad'e approximation. Block bi--orthogonality.Modified Krylov spaces. The Conjugate Gradient Squaredalgorithm. Extensions of BiCG. The Quasi MinimalResidual algorithm. CMRH. Which method touse?. Complex linear systems. Krylov methodson parallel computers. Bibliographical comments.Preconditioning. Introduction. Thediagonal 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. Fourieranalysis of BSSOR. The incomplete Cholesky decomposition.The general decomposition. Incomplete decomposition ofH--matrices. Incomplete decomposition of non--symmetric matrices.Different incomplete decomposition strategies. Finite differencematrices. Fourier analysis of IC(,). Comparison ofperiodic and Dirichlet boundary condi- tions. Axelsson'sresults. The modified incomplete Cholesky decomposition.The DKR preconditioner. Analysis of DKR.Fourier analysis of DKR. Extensions of DKR. Therelaxed incomplete Cholesky decomposition. More on the incompletedecompositions for the model problem. Stability of incompletedecomposition. The generalized SSOR preconditioner.Incomplete decomposition of positive definite matrices. Di#erentorderings for IC. Experimental results. Theoryfor model problems. Value dependent orderings.Multicolor orderings. The repeated Red--Black decomposition.Description of the methods. Analysis of RRB. Theblock incomplete Cholesky decomposition. Block tridiagonal matrices.Pointwise equivalent decomposition. The modifiedincomplete block decomposition. Block incomplete decomposition forH--matrices. Generalization of the block incomplete decomposition.Fourier analysis of INV and MINV. Axelsson's results.Block--size reduction. The block Cholesky decomposition for Dproblems. Point preconditioners. D blockpreconditioners. D point preconditioners. D blockpreconditioners. Nested factorization. The ACPpreconditioner for D problems. The preconditioner of Appleyard,Cheshire and Pol- lard. Improvements of ACP.Sparse approximate inverses. The sparse inverses of Huckle andGrote. The sparse inverses of Gould and Scott. The sparseinverses of Chow and Saad. Sparse approximate inverses for symmetricmatrices. The sparse inverses of Benzi, Meyer and Tuma. Polynomialpreconditioners. Truncated Neumann series. Theminmax polynomial. Least squares polynomials. Stableevaluation of polynomials. A polynomial independent of eigenvalueestimates. Adaptive algorithms for SPD matrices. Polynomials forsymmetric indefinite problems. Polynomials for non--symmetric problems.Double preconditioners. Other ideas.ADI preconditioner. ADDKR preconditioner. Elementby element preconditioner. Fast solvers. Wavelets.Vector and parallel computing. Vectorizationof IC(,). Parallel orderings. Vectorization ofINV. Twisted incomplete block factorizations.Incomplete block cyclic reduction. A massively parallelpreconditioner. Bibliographical comments. Multigridmethods. 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 ofcomponents. 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 andmultilevel methods. Introduction to domain decomposition.Schwarz methods. The classical Schwarz alternating method.The matrix form of the Schwarz alternating method. The rate ofconvergence. Other boundary conditions.Parallelizing multiplicative Schwarz. The additive Schwarz method.Adding a coarse mesh correction. An additive Schwarz preconditionerfor parabolic problems. Algebraic domain decomposition methods withoutoverlapping. Exact solvers for the subdomains. Approximatesolvers for the subdomains. Approximate Schur complements in the twosubdomains 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--Neumannpreconditioner. Dependence on the aspect ratio. Dependenceon the coefficients. Probing. INV and MINVapproximations. The Schur complement for more general problems.Approximations of Schur complements with many subdomains. Inexactsubdomain solvers. Domain decomposition with boxes.The Bramble, Pasciak and Schatz preconditioner. Vertex spacepreconditioners. A block Red--Black DD preconditioner.Multilevel preconditioners. Additive multilevel Schwarzpreconditioners. Multilevel ILU preconditioners. Bibliographicalcomments. References. Index.