Общее
Yosef Saad. Iterative Methods for Sparse Linear Systems
Тематический план
- Общее
- Individual project
- Module 1. Lecture 1
Module 1. Lecture 1
Background in Linear Algebra. Basic definitions. Types and structures of square matrices.
- Lectures 2-4
Lectures 2-4
Vector and matrix norms. Range and kernel. Existence of solution. Orthonormal vectors. Gram-Schmidt process. Eigenvalues and their multiplicities. Basic matrix factorizations and canonical forms: QR, diagonal form, Jordan form, Schur form, SVD, LU, Cholessky. Properties of positive definite matrices, normal and Hermitian matrices. Perturbation analysis and condition number. Errors and costs.
- Lectures 5-7
Lectures 5-7
Lectures 5-6. Discretization of partial differential equations (PDEs). Finite differences. 1D Poisson’s equation. 2D Poisson’s equation. Overview of Finite element method. Assembly process in FEM.
Lecture 7. Structures and graphs representations of sparse matrices. Storage schemes for sparse matrices. Algorithms for matrix by vector multiplication.
- Module 2. Lectures 8-10
Module 2. Lectures 8-10
Lecture 8. Comparison of direct and iterative methods. Overview of direct solution methods. Direct sparse methods (Gaussian elimination with partial pivoting).
Lecture 9. Iterative methods: general idea and convergence criterion. Classic iterative methods: Jacobi, Gauss-Seidel, Successive Over Relaxation (SOR), Symmetric Successive Over Relaxation (SSOR). Properties of diagonally dominant matrices, location of matrix eigenvalues. Convergence criteria for iterative methods.
Lecture 10. Projection methods: general formulation of a projection method. One-dimensional projection methods: Steepest Descent method (SDM), Minimal Residual Iteration method (MRIM), Residual Norm Steepest Descent method (RNSD).
- Module 3. Lectures 11-13
Module 3. Lectures 11-13
Lecture 11. Krylov subspace methods. Definition of Krylov subspace. General formulation of a Krylov subspace method. The process of Arnoldi orthogonalization to form a basis for Krylov subspace. Arnoldi relation and its properties.
Lecture 12. Methods based on Arnoldi orthogonalization: Full Orthogonalization method (FOM) and Generalized Minimal Residual method (GMRES).
Lecture 13. Givens rotations in GMRES .Calculation of residual in FOM and GMRES. Residual polynomials