Krylov Subspace Methods for Linear Systems. Principles of Algorithms

Description

Preface Acknowledgements Contents 1 Introduction to Numerical Methods for Solving Linear Systems 1.1 Linear Systems 1.1.1 Vector Norm 1.1.2 Matrix Norm 1.2 Condition Number 1.3 Direct Methods 1.3.1 LU Decomposition 1.3.2 LU Decomposition with Pivoting 1.3.3 Iterative Refinement 1.4 Direct Methods for Symmetric Linear Systems 1.4.1 Cholesky Decomposition 1.4.2 LDL Decomposition 1.5 Direct Methods for Large and Sparse Linear Systems 1.6 Stationary Iterative Methods 1.6.1 The Jacobi Method 1.6.2 The Gauss–Seidel Method 1.6.3 The SOR Method 1.6.4 Convergence of the Stationary Iterative Methods 1.7 Multigrid Methods 1.8 Krylov Subspace Methods 1.9 Orthogonalization Methods for Krylov Subspaces 1.9.1 The Arnoldi Process 1.9.2 The Bi-Lanczos Process 1.9.3 The Complex Symmetric Lanczos Process 1.9.4 The Lanczos Process 2 Some Applications to Computational Science and Data Science 2.1 Partial Differential Equations 2.1.1 Finite Difference Methods 2.1.2 The Finite Element Method 2.1.3 Weak Form 2.1.4 Derivation of Linear Systems 2.1.5 Example 2.2 Computational Physics 2.2.1 Large-Scale Electronic Structure Calculation 2.2.2 Lattice Quantum Chromodynamics 2.3 Machine Learning 2.3.1 Least-squares Regression 2.3.2 Least-squares Classification 2.4 Matrix Equations 2.5 Optimization 2.5.1 Tensor Notations 2.5.2 Newton's Method on Euclidean Space 2.5.3 Newton's Method on Riemannian Manifold 3 Classification and Theory of Krylov Subspace Methods 3.1 Hermitian Linear Systems 3.1.1 The Conjugate Gradient (CG) Method 3.1.2 The Conjugate Residual (CR) Method 3.1.3 The Minimal Residual (MINRES) Method 3.2 Complex Symmetric Linear Systems 3.2.1 The Conjugate Orthogonal Conjugate Gradient (COCG) Method 3.2.2 The Conjugate Orthogonal Conjugate Residual (COCR) Method 3.2.3 The Quasi-Minimal Residual (QMR_SYM) Method 3.3 Non-Hermitian Linear Systems 3.3.1 The Bi-Conjugate Gradient (BiCG) Method 3.3.2 The Composite Step Bi-Conjugate Gradient (CSBiCG) Method 3.3.3 The Bi-Conjugate Residual (BiCR) Method 3.3.4 The Quasi-Minimal Residual (QMR) Method 3.3.5 The Generalized Minimal Residual (GMRES) Method 3.3.6 The Generalized Conjugate Residual (GCR) Method 3.3.7 The Full Orthogonalization Method (FOM) 3.3.8 Product-Type Krylov Subspace Methods 3.3.9 Induced Dimension Reduction (IDR(s)) Method 3.3.10 Block Induced Dimension Reduction (Block IDR(s)) Method 3.4 Other Krylov Subspace Methods 3.4.1 Krylov Subspace Methods for Normal Equations 3.5 Preconditioning Techniques 3.5.1 Incomplete Matrix Decomposition Preconditioners 3.5.2 Approximate Inverse Preconditioners 3.5.3 Matrix Polynomial Preconditioners 3.5.4 Preconditioners Based on Stationary Iterative Methods 3.5.5 Reorderings for Preconditioners 4 Applications to Shifted Linear Systems 4.1 Shifted Linear Systems 4.2 Shifted Hermitian Linear Systems 4.2.1 The Shifted CG Method 4.2.2 The Shifted CR Method 4.2.3 The Shifted MINRES Method 4.3 Shifted Complex Symmetric Linear Systems 4.3.1 The Shifted COCG Method 4.3.2 The Shifted COCR Method 4.3.3 The Shifted QMR_SYM Method 4.4 Shifted Non-Hermitian Linear Systems 4.4.1 The Shifted BiCG Method 4.4.2 The Shifted BiCGSTAB Method 4.4.3 The Shifted GMRES Method 4.4.4 The Shifted IDR(s) Method 5 Applications to Matrix Functions 5.1 Jordan Canonical Form 5.2 Definition and Properties of Matrix Functions 5.3 Matrix Square Root and Matrix pth Root 5.3.1 Matrix Square Root 5.3.2 Matrix pth Root 5.4 Matrix Exponential Function 5.4.1 Numerical Algorithms for Matrix Exponential Functions 5.4.2 Multiplication of a Matrix Exponential Function and a Vector 5.5 Matrix Trigonometric Functions 5.6 Matrix Logarithm 5.7 Matrix Fractional Power Appendix Software Appendix References Index