Iterative Methods for Sparse Linear Systems Second Edition

1 Iterative Methodsfor SparseLinear SystemsSecond Edition +07 Yousef SaadCopyrightc 2003 by the Society for Industrial and Applied MathematicsContentsPrefacexiiiPreface to Second Edition ..xiiiPreface to first Edition ..xix1 Background in Linear .. Matrices and Eigenvalues .. of Matrices .. Inner Products and Norms .. Norms .. , Range, and Kernel .. Vectors and Subspaces .. Forms of Matrices .. to the Diagonal Form .. Jordan Canonical Form .. Schur Canonical Form .. to Powers of Matrices .. and Hermitian Matrices .. Matrices .. Matrices .. Matrices, M-Matrices .. Matrices .. Operators .. and Null Space of a Projector .. Representations .. and Oblique Projectors .. of Orthogonal Projectors .. Concepts in Linear Systems .. of a Solution .. Analysis.

2 412 Discretization of Differential Equations .. Operators .. Convection Diffusion Equation .. Difference Methods .. Approximations .. Schemes for the Laplacean Operator . Differences for 1-D Problems .. Schemes .. Differences for 2-D Problems .. Poisson Solvers .. finite Element Method .. Generation and Refinement .. Volume Method ..693 Sparse .. Representations .. and Adjacency Graphs .. of PDE Matrices .. and Reorderings .. Concepts .. with the Adjacency Graph .. Reorderings .. Schemes .. Sparse Matrix Operations .. Direct Solution Methods .. degree ordering .. Dissection ordering .. Problems ..984 Basic Iterative , Gauss-Seidel, and SOR .. Relaxation Schemes .. Matrices and Preconditioning .. Convergence Result .. Splittings.

3 Dominant Matrices .. Positive Definite Matrices .. A and Consistent Orderings .. Direction Methods .. 1275 Projection Definitions and Algorithms .. Projection Methods .. Representation .. Theory .. Optimality Results .. in Terms of Projectors .. Error Bound .. Projection Processes .. Descent .. Residual (MR) Iteration .. Norm Steepest Descent .. and Multiplicative Processes .. 1476 Krylov Subspace Methods Part .. Subspaces .. s Method .. Basic Algorithm .. Implementations .. s Method for Linear Systems (FOM) .. 1: Restarted FOM .. 2: IOM and DIOM .. Basic GMRES Algorithm .. Householder Version .. Implementation Issues .. of GMRES .. 1: Restarting.

4 2: Truncated GMRES Versions .. between FOM and GMRES .. smoothing .. for complex Systems .. Symmetric Lanczos Algorithm .. Algorithm .. with Orthogonal Polynomials .. Conjugate Gradient Algorithm .. and Theory .. Formulations .. Estimates from the CG Coefficients .. Conjugate Residual Method .. , ORTHOMIN, and ORTHODIR .. Faber-Manteuffel Theorem .. Analysis .. Chebyshev Polynomials .. Chebyshev Polynomials .. of the CG Algorithm .. of GMRES .. Krylov Methods .. 2187 Krylov Subspace Methods Part Biorthogonalization .. Algorithm .. Implementations .. Lanczos Algorithm for Linear Systems .. BCG and QMR Algorithms .. Biconjugate Gradient Algorithm .. Residual Algorithm.

5 Variants .. Gradient Squared .. QMR (TFQMR) .. 2478 Methods Related to the Normal Normal Equations .. Projection Methods .. on the Normal Equations .. s Method .. Gradient and Normal Equations .. Problems .. 2689 Preconditioned .. Conjugate Gradient .. Symmetry .. Implementations .. GMRES .. GMRES .. GMRES .. Preconditioning .. of Right and Left Preconditioning .. Variants .. GMRES .. CG for the Normal Equations .. Concus, Golub, and Widlund Algorithm .. 29210 Preconditioning .. , SOR, and SSOR Preconditioners .. Factorization Preconditioners .. LU Factorizations .. Fill-in ILU (ILU(0)) .. of Fill and ILU(p) .. with Regular Structure.

6 ILU (MILU) .. Strategies and ILUT .. ILUT Approach .. Details .. ILUTP Approach .. ILUS Approach .. Crout ILU Approach .. Inverse Preconditioners .. the Inverse of a Sparse Matrix .. Iteration .. Algorithms .. Considerations .. of Self Preconditioned MR .. Inverses via bordering .. inverses via orthogonalization: AINV .. a Preconditioner .. for ILU .. permutations .. reorderings .. Preconditioners .. Matrices .. Matrices .. for the Normal Equations .. , SOR, and Variants .. (0) for the Normal Equations .. Gram-Schmidt and ILQ .. 36011 Parallel .. of Parallelism .. Functional Units .. Processors .. and Distributed Computing.

7 Of Parallel Architectures .. Memory Computers .. Memory Architectures .. of Operations .. Products .. CSR and CSC Formats .. in the Diagonal Format .. Ellpack-Itpack Format .. Jagged Diagonal Format .. Case of Distributed Sparse Matrices .. Preconditioning Operations .. in Forward Sweeps .. Scheduling: the Case of 5-Point Matrices . Scheduling for Irregular Graphs .. 38812 Parallel .. Preconditioners .. Preconditioners .. Polynomials .. Polynomials .. Polynomials .. Nonsymmetric Case .. Ordering .. of Red-Black Systems .. for General Sparse Matrices .. ILU .. ILU and SSOR .. Techniques .. Inverses .. Techniques .. Row Projection Preconditioners.

8 41913 Multigrid .. and spectra of model problems .. s iteration .. Jacobi iteration .. iteration .. operations .. multigrid techniques .. problems and smoothers .. cycles .. and W-cycles .. Multigrid .. for the two-grid cycle .. important subspaces .. analysis .. Multigrid .. in AMG .. in AMG .. coarse spaces in AMG .. via Multilevel ILU .. vs Krylov Methods .. 46414 Domain Decomposition .. of Partitionings .. of Techniques .. Solution and the Schur Complement .. Gaussian Elimination .. of the Schur Complement .. Complement for Vertex-Based Complement for finite -Element Partitionings Complement for the model problem .. Alternating Procedures.

9 Schwarz Procedure .. Schwarz Preconditioning .. Schwarz Procedure .. Complement Approaches .. Preconditioners .. Vertex-Based Schur Complements Matrix Methods .. Partitioning .. Definitions .. Approach .. Techniques .. Theory Techniques .. 507 References514 Index535xiiCONTENTSP reface to the Second editionIn the six years that passed since the publication of the first Edition of this book, Iterative Methods for Linear Systems have made good progress in scientific and engi-neering disciplines. This is due in great part to the increased complexity andsize ofthe new generation of Linear and nonlinear Systems which arise from typicalappli-cations. At the same time, parallel computing has penetrated the same applicationareas, as inexpensive computer power became broadly available and standard com-munication languages such as MPI gave a much needed standardization.

10 This hascreated an incentive to utilize Iterative rather than direct solvers becausethe prob-lems solved are typically from 3-dimensional models for which direct solversoftenbecome ineffective. Another incentive is that Iterative Methods are far easier to im-plement on parallel computers,Though Iterative Methods for Linear Systems have seen a significant maturation,there are still many open problems. In particular, it still cannot be stated thatanarbitrary Sparse Linear system can be solved iteratively in an efficient way. If physicalinformation about the problem can be exploited, more effective and robust methodscan be tailored for the solutions. This strategy is exploited by multigrid Methods . Inaddition, parallel computers necessitate different ways of approachingthe problemand solution algorithms that are radically different from classical new texts on the subject of this book have appeared since the first these, are the books by Greenbaum [154], and Meurant [209].