Till KTH:s startsida Till KTH:s startsida

Old course overview (HT2015)

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

  • A selection of chapters in 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. It is available in Kårbokhandeln.
  • "Lecture notes in numerical linear algebra" by Elias Jarlebring  (PDF-files below)

Prerequisites

  • A basic course in Numerical Methods, for instance SF1544 (or equivalent).
  • Recommended but not strictly necessary: A continuation course in numerical analysis, for instance SF2520 applied numerical methods, which can be read in parallel.

This course is elective for all master's programmes at KTH. The course is conditionally elective in the second year of the Master's programme in applied and computational mathematics, and mandatory for the  Computational mathematics (beräkningsmatematik) track. It is conditionally elective for the Master's programme in Computer simulation for science and engineering (COSSE, TDTNM). This course is suitable for students taking the programme Computer science and engineering (CDATE) if you have taken the course SF1626 Calculus in Several Variable (flervariabelanalys).

This course is a subset of the PhD-level course SF3580 - Numerical linear algebra which is taught jointly.

Main course contents

  • Numerical methods for large sparse eigenvalue problems:  
    • Topics: Power method, Rayleigh quotient iteration, Arnoldi's method, Repeated Gram-Schmidt, Modified Gram-Schmidt, convergence characterization for Arnoldi's method for eigenvalue problems
    • Reading instructions sparse eigenvalue problems: [TB] Chapter 8, 24,27,34,36
    • Notes on variants of the Gram-Schmidt orthogonalization process: Handwritten notes PDF
    • "Lecture notes in Numerical linear algebra", Chapter Convergence of the Arnoldi method for eigenvalue problems (PDF)
  • Numerical methods for large sparse linear systems of equations
  • Numerical methods for dense eigenvalue problems
  • Numerical methods for functions of matrices

See also background / fundamentals in background.pdf.

Homework

The course contains three sets of mandatory 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).

The links to PDF-files will be updated during the course.

Exam

Exam preparation questions (PDF)

Old exams

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 bonus points are valid until but not including the regular exam the following year.

Weekly plan

Preliminary contents per week: This plan will be updated during the course.

Week 45:

Course introduction, intro to eigenvalue problems:

Orthogonalization, Arnoldi, Krylov methods, convergence of Arnoldi method

Lecture 1:

  • Introduction to the course, basic eigenvalue algorithms (power method, Rayleigh quotient iteration, TB Lecture 27 + non-symmetric case). Slides (PDF).

Lecture 2:

Lecture 3:

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

Week 46:

Lanczos method, Introduction to iterative methods for linear systems

Lecture 4:

  • Convergence of Arnoldi method continued. Derivation of the Lanczos method.

Lecture 5:

  • Iterative methods for linear systems of equations:
    • Derivation of GMRES, and preparation for convergence. 
    • Additional notes related to GMRES

Homework 1 due on the day of Lecture 5.

Week 47:

Linear systems (Arnoldi / GMRES), convergence

Lecture 6:

Lecture 7:

Week 48:

Lecture 8:

  • BiCG, Preconditioning

Lecture 9:

Homework 2 due on Friday Nov. 27.

Week 49:

Lecture 10:

  • QR-method: Phase 2 (Hessenberg QR), acceleration, slides (PDF). Illustration of QR-factorization with givens rotators:

Lecture 11:

Week 50:

Lecture 12: Matrix functions

  • Fundamentals continued (Jordan definition, Cauchy integral definition)
  • The Schur-Parlett method

Lecture 13: Matrix functions

  • Newton-methods for the matrix square root and matrix sign function
  • Scaling-and-squaring for the matrix exponential. Video illustration: (The matrix-matrix multiply count at the end of the video is off by one.)

Homework 3 is due on the day of Lecture 13.

Week 51:

Lecture 14: Matrix functions

  • Krylov methods for matrix functions illustration video (mp4)
  • Application for solving ODEs

Other