Till KTH:s startsida Till KTH:s startsida

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

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

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:

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:

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:

Homework 2 due during week 48.

Week 49:

Lecture 9: QR-method continued

Lecture 10:

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.

Other