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:
  
  • Notes on variants of the Gram-Schmidt orthogonalization process
  • Pseudo-code for GMRES
  • Additional notes related to GMRES
  • Additional notes related for the analysis of Newton's method for matrix sign function
  • Further notes to be published later

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:

• Introduction to the course (PDF-slides)

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:

• Introduction to the convergence of the Arnoldi method (PDF-slides)

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).