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.
Literature
- 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
Homework
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
Exam
Exam preparation questions (PDF) version 2014-12-30 updated 2015-01-07
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
Weekly plan
Preliminary contents per week:
Week 45:
Course introduction, intro to eigenvalue problems:
Orthogonalization, Arnoldi, Krylov methods,
Lecture 1:
Lecture 2:
- Introduction to the Arnoldi method for eigenvalue problems (PDF-slides)
- Notes on variants of the Gram-Schmidt orthogonalization process
Week 46:
Convergence of Arnoldi's method for eigenvalue problems
Introduction to iterative methods for linear systems
Lecture 3:
Lecture 4:
- 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.
Week 47:
Linear systems (Arnoldi / GMRES), convergence
Lecture 5:
- Convergence of GMRES
- Derivation of CG
Lecture 6:
- Convergence of CG: Orthogonality, optimality and bounds
Week 48:
Lecture 7:
- CGN, BiCG
Lecture 8:
- Preconditioning
- Introduction to QR-method for eigenvalue problems
- QR-method intro (slides)
Homework 2 due during week 48.
Week 49:
Lecture 9: QR-method continued
- QR-method:
- Hessenberg reduction, Hessenberg QR
- Shifts
- QR-method part 2 (slides)
Lecture 10:
- QR-method: Convergence
- Introduction to functions of matrices (slides)
Week 50:
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.
Week 51:
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.
- Schur-Parlett method
- Krylov methods for matrix functions (PDF and illustration video)
Other
- 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).