# 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. T**ime 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).