Тематический план
-
-
- Lecture 1. Background in Linear Algebra. Basic definitions. Types and structures of square matrices. Vector and matrix norms.
- Lecture 2. Range and kernel. Existence of Solution. Orthonormal vectors. Gram-Schmidt process. Thin and full QR-factorization.
- Lecture 3. Eigenvalues and their multiplicities. Canonical forms by similarity transformation: diagonal form, Jordan form, Schur form. Other matrix factorizations: SVD, LU, Cholessky. Positive definite matrices.
- Lecture 4. Properties of normal and Hermittian matrices. Powers of matrices. Perturbation analysis and condition number. Errors and costs.
- Lecture 5. Structures and graphs representations of sparse matrices.
- Lecture 6. Storage schemes for sparse matrices. Algorithms for matrix by vector multiplication.
-
- Lecture 7. Comparison of direct and iterative methods. Overview of direct solution methods. Direct sparse methods (Gaussian elimination with partial pivoting).
- Lectures 8. Discretization of partial differential equations (PDEs). Finite difference method on the example of Poisson’s equation. Overview of finite element method.
- Lecture 9. Iterative methods: general idea and convergence criterion. Classic iterative methods: Jacobi, Gauss-Seidel, Successive Over Relaxation (SOR), Symmetric Successive Over Relaxation (SSOR).
- 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).
- Lecture 11. Krylov subspace methods. Definition of Krylov suspace. General formulation of a Krylov subspace method. The process of Arnoldi orthogonalization. Methods based on Arnoldi process: Full Orthogonalization method (FOM).
- Lecture 12. Methods based on Arnoldi process: Generalized Minimal Residual method (GMRES). Givens rotations in GRMRES. Calculation of residual in FOM and GMRES. Residual polynomials.
- Lecture 13. Lanczos orthogonalization for symmetric systems. Lanczos methods for symmetric systems: Direct Lanczos, Conjugate Gradient (CG), Conjugate Residual (CR), Generalized Conjugate Residual (GCR). Lanczos biorthogonalization for nonsymmetric systems. Lanczos methods for nonsymmetric systems: Classic Lanczos, Biconjugate Gradient method (BiCG). Overview: Efficient and optimal methods. Basic ideas of preconditioning technique. Examples of preconditioners.