Old course overview (HT2015)

[IMAGE]

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
* Topics: GMRES, CG, CGN, BiCG, convergence of Krylov methods, preconditioning
* Reading instructions: [TB] Chapter 32, 35, 38-40
* Additional notes related to GMRES (PDF new)

* Numerical methods for dense eigenvalue problems
* Topics: QR-method, Hessenberg reduction, implicit QR-method
* Reading instructions QR-method: [TB] Chapter 28-29,
* ""Lecture notes in Numerical linear algebra"", Chapter improvements of the QR-method (PDF updated 2015-11-23)


* Numerical methods for functions of matrices
* Topics: Taylor definition, Jordan definition, Contour integral definition, Schur-Parlett method, scaling-and-squaring for the matrix exponential, methods for the matrix square root, methods for the sign function
* ""Lecture notes in Numerical linear algebra"", Chapter Numerical methods for matrix functions (PDF) updated 2014-12-11

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.

* Homework 1: sparse eigenvalue problems (PDF). You will need arnoldi.m
* Homework 2: Iterative methods for linear systems (PDF updated 2015-11-23). You will need lshape_mod.mat
* Homework 3: QR-method and matrix functions (PDF). You will need alpha_example.m, naive_hessenberg_red.m, and schur_parlett.m

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:

* Introduction to the Arnoldi method for eigenvalue problems (PDF-slides)
* Variants of the Gram-Schmidt orthogonalization process: hand-written notes (PDF)
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:

* Convergence of GMRES
* Introduction to Conjugate gradients: CG Illustration video (mp4) https://people.kth.se/~eliasj/cg_demo1.mp4

Lecture 7:

* Convergence of CG: Orthogonality, optimality and bounds
* CGN. CGN illustration video (mp4) https://people.kth.se/~eliasj/cgn_demo.mp4

Week 48:

Lecture 8:

* BiCG, Preconditioning
Lecture 9:

* QR-method intro (phase 1) slides (PDF)
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: https://www.math.kth.se/~eliasj/qr_factorization_givens.mp4

Lecture 11:

* QR-method: convergence slides (PDF), illustration of unnormalized simultaneous iteration (mp4) https://people.kth.se/~eliasj/unnorm_simit_demo0.mp4

* Introduction to functions of matrices: three equivalent definitions
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.)
https://people.kth.se/~eliasj/expm_demo0.mp4

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 http://people.kth.se/~eliasj/krylov_matfun_approx.mp4

Other
* An enthusiastic TED-talk about the beauty of matrices: TED-talk by Margot Gerritsen (Stanford).
* Large-scale matrix computations in networks: a youtube seminar by David Gleich
* Administration and course registration: students affairs office of the mathematics department[IMAGE]
* The course description of a related course DN2230 (which is no longer offered).