Welcome

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 focus on detailed understanding about the performance of these methods when they are applied to large-scale systems and study topics such as convergence, accuracy and efficiency.

Teachers: Elias Jarlebring and Siobhan Correnty.

Course literature

Block 1:

block1.pdf Download block1.pdf

Block 2:

block2.pdf Download block2.pdf

Block 3:

block3.pdf Download block3.pdf

Block 4:

block4.pdf Download block4.pdf

Block 5: (Only for PhD students taking SF3580)

block5_SF3580.pdf Download block5_SF3580.pdf

Course information

Homework & bonus points rules

A complete list of video material: Video material in the course

Slides from Meetings / lectures: https://canvas.kth.se/courses/42754/files/folder/lecture_slides

Abbreviations and links can be found at the end of this page.

Course plan

Week 44

Meeting 1: Lecture
- Reading: block1.pdf: §1.1 (except §1.1.7)
- Contents: Course Intro + RQ + PM + Conv theory PM
- Recommended exercises: AL17: 1-10, AL19: 1-2, 1-3, AL20: 1-6a, AL21 1-1a-c (abbreviations and links at the bottom of this page)
Meeting 2: Lecture
- Reading: block1.pdf: §1.1,§1.3
- Contents: Inv. it + RQI + RR + AM intro + CGS + RGS
- Recommended exercises: ALW20: 1-17, 1-2, 1-26 (julia only), ALW19: 1-2
Meeting 3: Lecture
- Reading: block1.pdf: §1.2,§1.3
- Contents: MGS, AF +AM.
- Recommended exercises: ALW20 1-10, 1-38, 1-21, 1-34, ALW21: 1-9
Week 1: Quiz 1: Background and a bit (optional)
Week 1: Quiz 2: Eigenvalue problem example: A first application in data analytics
Week 1: Quiz 3: The minimization intepretation of the Rayleigh Quotient
Week 1: Quiz 4 Rayleigh-Ritz method convergence theory

Week 45

Meeting 4: Lecture
- Reading: block1.pdf: §1.4
- Contents: Convergence AM + shift-and-invert
- Recommended exercises: AL20: 1-33, 1-46, AL19 1-31b, 1-39
Meeting 5: World café workshop: Block 1
- More information follows
Week 2: Quiz 1: Lanczos method derivation
Week 2: Quiz 2: Breakdown in Arnold's method
Week 2: Quiz 3: (skip)
Week 2: Quiz 4: Block 2 application: CPU-socket

Week 46

Deadline HW 1

Meeting 6: Lecture
- Reading: block2.pdf: 2.1.1 + 2.1.2
- Contents: Linsys Intro + GMRES + Conv theory
- Recommended exercises: AL21: 2-8, AL18: 2-15
Meeting 7: Lecture
- Reading: block2.pdf §2.2-2.2.2.
- Contents: CG
- Recommended exercises: AL20: 2-4, 2-44, 2-29, 2-57, AL18: 2-20a, 2-24
Meeting 8: Lecture
- Reading: block2.pdf §2.2-2.2.2 + §2.3
- Contents: CG convergence + CGN
- Recommended exercises: AL20: 2-8, 2-50, AL21: 2-52, 2-99, AL21: 2-23, 2-25, 2-37, AL20: 2-51, 2-53,
Week 3 quiz 1: Preconditioning for GMRES
Week 3 quiz 2: Arnoldi-Tikhonov regularization application
Week 3 quiz 3: Preconditioning for CG part 1
Week 3 quiz 4: Preconditioning for CG part 2

Week 47

Meeting 9: Lecture
- Reading: block3.pdf §3.2.1
- Contents: QR-method. Improvement 1: Phase 1
- Recommended exercises: AL21: 3-7, 3-9, 3-14, AL20: 3-12, 3-16, 3-32, 3-40
Meeting 10: World café workshop: Block 2
Week 4 quiz 1: GMRES convergence single outlier
Week 4 quiz 2: CG history
(skip)
Week 4 quiz 4: BiCG method derivation

Week 48

Deadline HW 2
Meeting 11: Lecture
- Reading: block3.pdf: §3.2.2
- Contents: QR-method: Phase 1 + Phase 2
- Recommended exercises: AL21: 3-19, 3-8,
Meeting 12: Lecture
- Reading: block3.pdf:
- Contents: Acceleration and convergence
- Reading block4.pdf
- Contents: Introduction to Matrix functions
Week 5 quiz 1: Intro to the QR-method by Driscoll
Week 5 quiz 2: QR factorization by Householder reflectors (by van de Gijn)
Week 5 quiz 3: Simultaneous iteration part 1: Normalized and unnormalized
Week 5 quiz 4: Simultaneous iteration part 2: Convergence of unnormalized (diagonal + triangular)
Week 5 quiz 5: Deflation in the QR-method (by van de Geijn)
Optional: Week 5 quiz 6: basic QR method and orthogonal iteration (optional)

Week 49

Meeting 13: Lecture
- Reading: block4.pdf: §4.1-§4.2
- Contents: Matrix functions + Matrix exponention + Mat sqrt + Mat sign
- Recommended exercises: AL18: 4-18, 4-23, AL21: 4-22, 4-30
Meeting 14: Lecture
- Reading: block4.pdf: §4.3
- Contents: Krylov approx for matrix functions. Exponential integrators applications
- Recommended exercises: AL21 4-24, AL17: 4-20
Week 6 quiz 1: phi-functions and exponential integrator applications
Week 6 quiz 2: FOM derivation (preparation for Krylov approx of matrix functions)