27.10.2005: Linear systems,Gaussian-elimination, LU-factorization, pivoting, PA=LU
03.11.2005: Cholesky-factorization, computational cost, examples of linear systems arising from discretizations of ODEs and PDEs, banded matrices, lower/upper bandwidth, LU-factorization of banded matrices
10.11.2005: Fill-in problems, e.g. arrow matrix, graphs and matrices, Example of large sparse linear system arising in Google PageRank, row- and column permutation equivalent to relabeling of graph, Level-set reorderings and Cuthill-McKee Links
Fast PageRank Computation Via a Sparse Linear System (Extended Abstract) by del Corso et al.
17.11.2005: Level-set orderings and reduction of bandwidth, Reverse Cuthill-McKee, envelope of a matrix and fill-in, Elimination graph and fill-in, Minimum degree algorithm, Storage schemes: Coordinate and CSR format.
24.11.2005: CSR and diagonal format, matrix vector multiplication in CSR. Classical iterative methods: General framework, A=M-N; fixed point iteration, matrix norms and spectral radius; methods of Jacobi and Gauss-Seidel
01.12.2005: Jacobi, Gauss-Seidel and SOR; application to discretized Poisson-equation; convergence anaylsis: weakly/strongly diagonally dominant matrix; reducible/irreducible matrix; property A
08.12.2005: Comparison of Jacobi and SOR assuming property A; optimal relaxation parameter; polynomial methods; polynomial of a matrix; spectral mapping theorem; Chebyshev acceleration
15.12.2005: Chebyshev polynomials and minimization of the spectral radius; Krylov subspaces; Krylov subspace methods: Find an optimal new iterate within the (affine) Krylov subspace x_0+K(A,r_0); different optimality criteria lead to different methods; Conjugate Gradients, geometric idea: minimization of quadratic functional; first idea: steepest descent
22.12.2005: Conjugate Gradients: steepest descent, orthogonal directions and zig-zagging; A-orthogonality and conjugate directions; minimization property; construction of conjugate directions by A-orthogonalization of the gradients; the CG-algorithm; speed of convergence
2.2.2006: Some remarks on multigrid: revisited example: Poisson equation; uses different grid sizes to obtain and improve approximate solutions. Solution operator, Restriction operator, Interpolation operator; V-cycle (MGV) and Full multigrid (FMG).
Friday, 3.2.2006: Written Exam: PK 4.1 (A-K) and PK 4.4 (L-Z)
