Pre-exam consultation 1: January 22, 12.00, room 201.
Pre-exam consultation 2: January 23, 12.00, room 201.
Exam: January 24 (time to be announced)
All remaining practical assignments can be submitted during consultations beform exam.
Background in Linear Algebra. Basic definitions.
Types and structures of quadratic matrices. 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. Basic matrix factorizations: SVD, LU, Cholessky.
Perturbation analysis and condition number.
Errors and costs. 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. Structures and graphs representations
of sparse matrices.
Storage schemes for sparse matrices. Algorithms
for matrix by vector multiplication. Comparison of direct and iterative
methods. Overview of direct solution methods. Direct sparse methods (Gaussian
elimination with partial pivoting).
Iterative methods: general idea and convergence
criterion. Basic 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. 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 6. Krylov subspace methods. Definition of Krylov suspace. 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 7. Methods based on Arnoldi orthogonalization: Full Orthogonalization method (FOM) and Generalized Minimal Residual method (GMRES). Calculation of residual in FOM and GMRES. Givens rotations in GMRES.
Lecture 8. Givens rotations in GMRES (continue).
Lanczos orthogonalization for symmetric systems. Lanczos methods for symmetric
systems: classic and direct. Derivation of Direct Lanczos method.
Lecture 9. Derivation of Conjugate Gradient method (CG) for systems with symmetric positive definite matrices. Generalization of CG for systems with Hermitian and nonsymmetric matrices: Conjugate Residual (CR), Generalized Conjugate Residual (GCR).
Lecture 10. Lanczos biorthogonalization for
nonsymmetric systems. Classic Lanczos method for nonsymmetric systems .
Derivation of Biconjugate Gradient method (BiCG). Overview: Efficient and
optimal methods. Basic ideas of preconditioning technique. Examples of
preconditioners: Jacobi, Gauss-Seidel, SOR and SSOR, incomplete
LU-factorization. Preconditioned Krylov subspace methods. Preconditioned
Conjugate Gradient method: PCG and Split PCG. Preconditioned Generalized Minimal Residual method,
algorithms of GRMES with left and right preconditioning