Old course overview (HT2014)
Welcome to this course
In this course we will learn some of the most common numerical techniques and algorithms used to efficiently solve problems expressed using large matrices. We will learn about the convergence and detailed understanding about the performance of these methods when they are applied to large-scale systems.
- Some chapters from the book "Numerical Linear Algebra", by Lloyd N. Trefethen and David Bau. ISBN: 0-89871-361-7, referred to as [TB] in the reading instructions below.
- Lecture notes on the convergence of the Arnoldi method for eigenvalue problems (PDF)
- Lecture notes on improvements of the QR-method (PDF).
- Parts from the book Matrix Computations, Golub, Van Loan (4th edition, 2013), ISBN: 978-1421407944, referred to as [GVL] below.
- Lecture notes on Krylov methods for matrix functions (PDF)
- Hand-written notes:
Main course contents
- Numerical methods for eigenvalue problems:
- Reading instructions sparse eigenvalue problems (Lecture 1-3): [TB] Chapter 8, 24,27,34,36, lecture notes on convergence of Arnoldi method
- If you have not heard of the QR-factorization you should read up on [TB] Chapter 7, 10.
- Reading instructions QR-method (Lecture 8-9): [TB] Chapter 28-29, lecture notes on QR-method (online)
- Hand-written notes on variants of the Gram-Schmidt orthogonalization process
- Numerical methods for linear systems of equations
- [TB] Chapter 32, 35, 38-40
- Hand-written notes on additional notes related to GMRES
- Numerical methods for functions of matrices
- [GVL] Sections 9.1.1-9.1.4, 9.2.3-9.2.5, 9.3.1, 9.4.1, 9.4.2
The course will contain three sets of homework, involving theory and programming (in MATLAB). The homework should be handed in as written reports with clear solutions to the problems. Bonus points for the exam will be awarded if the homework is handed in on the specified deadlines.The reports are expected to be clearly written and it is highly recommended that they are prepared with a computer (word/latex or similar, not hand-written).
- Homework 1: sparse eigenvalue problems. You will need arnoldi.m
- Homework 2: Iterative methods for linear systems. You will need lshape_mod.mat
- Homework 3: QR-method and matrix functions. You will need alpha_example.m, naive_hessenberg_red.m, and find_q.m
The exam is four hours. No aids are allowed during the exam (in particular no notes, no calculator, no book).
Bonus points for the exam will be awarded depending on when you hand in the homework. If you have passed all homeworks on time, a total of 6 bonus points will be awarded.
The exam of DN2233 (PDF) - a course with related contents but is no longer given
Preliminary contents per week:
Course introduction, intro to eigenvalue problems:
Orthogonalization, Arnoldi, Krylov methods,
- Introduction to the Arnoldi method for eigenvalue problems (PDF-slides)
- Notes on variants of the Gram-Schmidt orthogonalization process
Convergence of Arnoldi's method for eigenvalue problems
Introduction to iterative methods for linear systems
- Derivation of the Lanczos method
- Iterative methods for linear systems of equations:
- Derivation of GMRES, and preparation for convergence.
- Additional notes related to GMRES
Homework 1 due during week 46.
Linear systems (Arnoldi / GMRES), convergence
- Convergence of GMRES
- Derivation of CG
- Convergence of CG: Orthogonality, optimality and bounds
- CGN, BiCG
- Introduction to QR-method for eigenvalue problems
- QR-method intro (slides)
Homework 2 due during week 48.
Lecture 9: QR-method continued
- Hessenberg reduction, Hessenberg QR
- QR-method part 2 (slides)
- QR-method: Convergence
- Introduction to functions of matrices (slides)
Lecture 11: Matrix functions
- Fundamentals for matrix functions: definitions, generalization of Taylors theorem
- interpolation property (illustration video)
- scaling-and-squaring for the matrix exponential
Homework 3 due during week 50.
Lecture: Matrix functions
- Matrix sign function
- Matrix square root
Lecture: Matrix functions. Note: The time and location of this lecture is not in the official schedule. Time and place: Friday, Dec. 19, 13:15-15:00, KTH Mathematics building, Lindstedsvägen 25, seminar room 3733.
- The course description of a related course DN2230 (which is no longer given).
- An enthusiastic TED-talk about the beauty of matrices: TED-talk by Margot Gerritsen (Stanford).