Krylov Subspace Methods for Linear Systems : Principles of Algorithms

'This book focuses on Krylov subspace methods for solving linear systems, which are known as one of the top 10 algorithms in the twentieth century, such as Fast Fourier Transform and Quick Sort (SIAM News, 2000). Theoretical aspects of Krylov subspace methods developed in the twentieth century are explained and derived in a concise and unified way. Furthermore, some Krylov subspace methods in the twenty-first century are described in detail, such as the COCR method for complex symmetric linear systems, the BiCR method, and the IDR(s) method for non-Hermitian linear systems. The strength of the book is not only in describing principles of Krylov subspace methods but in providing a variety of applications: shifted linear systems and matrix functions from the theoretical point of view, as well as partial differential equations, computational physics, computational particle physics, optimizations, and machine learning from a practical point of view. The book is self-contained in that basic necessary concepts of numerical linear algebra are explained, making it suitable for senior undergraduates, postgraduates, and researchers in mathematics, engineering, and computational science. Readers will find it a useful resource for understanding the principles and properties of Krylov subspace methods and correctly using those methods for solving problems in the future.' Sommario fornito dall'editore Preface 6 Acknowledgements 9 Contents 10 1 Introduction to Numerical Methods for Solving Linear Systems 13 1.1 Linear Systems 13 1.1.1 Vector Norm 14 1.1.2 Matrix Norm 14 1.2 Condition Number 16 1.3 Direct Methods 16 1.3.1 LU Decomposition 17 1.3.2 LU Decomposition with Pivoting 18 1.3.3 Iterative Refinement 20 1.4 Direct Methods for Symmetric Linear Systems 21 1.4.1 Cholesky Decomposition 21 1.4.2 LDL Decomposition 22 1.5 Direct Methods for Large and Sparse Linear Systems 24 1.6 Stationary Iterative Methods 25 1.6.1 The Jacobi Method 26 1.6.2 The Gauss–Seidel Method 27 1.6.3 The SOR Method 27 1.6.4 Convergence of the Stationary Iterative Methods 28 1.7 Multigrid Methods 30 1.8 Krylov Subspace Methods 31 1.9 Orthogonalization Methods for Krylov Subspaces 35 1.9.1 The Arnoldi Process 35 1.9.2 The Bi-Lanczos Process 38 1.9.3 The Complex Symmetric Lanczos Process 39 1.9.4 The Lanczos Process 40 2 Some Applications to Computational Science and Data Science 42 2.1 Partial Differential Equations 42 2.1.1 Finite Difference Methods 42 2.1.2 The Finite Element Method 53 2.1.3 Weak Form 54 2.1.4 Derivation of Linear Systems 55 2.1.5 Example 58 2.2 Computational Physics 62 2.2.1 Large-Scale Electronic Structure Calculation 62 2.2.2 Lattice Quantum Chromodynamics 63 2.3 Machine Learning 67 2.3.1 Least-squares Regression 67 2.3.2 Least-squares Classification 71 2.4 Matrix Equations 74 2.5 Optimization 76 2.5.1 Tensor Notations 77 2.5.2 Newton's Method on Euclidean Space 78 2.5.3 Newton's Method on Riemannian Manifold 79 3 Classification and Theory of Krylov Subspace Methods 84 3.1 Hermitian Linear Systems 84 3.1.1 The Conjugate Gradient (CG) Method 84 3.1.2 The Conjugate Residual (CR) Method 94 3.1.3 The Minimal Residual (MINRES) Method 97 3.2 Complex Symmetric Linear Systems 101 3.2.1 The Conjugate Orthogonal Conjugate Gradient (COCG) Method 102 3.2.2 The Conjugate Orthogonal Conjugate Residual (COCR) Method 103 3.2.3 The Quasi-Minimal Residual (QMR_SYM) Method 108 3.3 Non-Hermitian Linear Systems 110 3.3.1 The Bi-Conjugate Gradient (BiCG) Method 112 3.3.2 The Composite Step Bi-Conjugate Gradient (CSBiCG) Method 115 3.3.3 The Bi-Conjugate Residual (BiCR) Method 118 3.3.4 The Quasi-Minimal Residual (QMR) Method 120 3.3.5 The Generalized Minimal Residual (GMRES) Method 122 3.3.6 The Generalized Conjugate Residual (GCR) Method 127 3.3.7 The Full Orthogonalization Method (FOM) 133 3.3.8 Product-Type Krylov Subspace Methods 134 3.3.9 Induced Dimension Reduction (IDR(s)) Method 143 3.3.10 Block Induced Dimension Reduction (Block IDR(s)) Method 151 3.4 Other Krylov Subspace Methods 157 3.4.1 Krylov Subspace Methods for Normal Equations 158 3.5 Preconditioning Techniques 162 3.5.1 Incomplete Matrix Decomposition Preconditioners 163 3.5.2 Approximate Inverse Preconditioners 169 3.5.3 Matrix Polynomial Preconditioners 170 3.5.4 Preconditioners Based on Stationary Iterative Methods 171 3.5.5 Reorderings for Preconditioners 172 4 Applications to Shifted Linear Systems 174 4.1 Shifted Linear Systems 174 4.2 Shifted Hermitian Linear Systems 176 4.2.1 The Shifted CG Method 176 4.2.2 The Shifted CR Method 178 4.2.3 The Shifted MINRES Method 180 4.3 Shifted Complex Symmetric Linear Systems 182 4.3.1 The Shifted COCG Method 182 4.3.2 The Shifted COCR Method 185 4.3.3 The Shifted QMR_SYM Method 185 4.4 Shifted Non-Hermitian Linear Systems 187 4.4.1 The Shifted BiCG Method 187 4.4.2 The Shifted BiCGSTAB Method 188 4.4.3 The Shifted GMRES Method 191 4.4.4 The Shifted IDR(s) Method 196 5 Applications to Matrix Functions 200 5.1 Jordan Canonical Form 200 5.2 Definition and Properties of Matrix Functions 202 5.3 Matrix Square Root and Matrix pth Root 205 5.3.1 Matrix Square Root 205 5.3.2 Matrix pth Root 208 5.4 Matrix Exponential Function 209 5.4.1 Numerical Algorithms for Matrix Exponential Functions 210 5.4.2 Multiplication of a Matrix Exponential Function and a Vector 212 5.5 Matrix Trigonometric Functions 213 5.6 Matrix Logarithm 214 5.7 Matrix Fractional Power 219 Appendix Software 221 Appendix References 222 222 Index 231