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 Jiayu Bian. For homework explanations / questions, please contact primarily Jiayu.

Course literature and video

Block 1:

block1.pdf

Block 2:

block2.pdf

Block 3:

block3.pdf

Block 4:

block4.pdf

Block 5: (Only for PhD students taking SF3580)

block5_SF3580.pdf

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

See also background.pdf

General course information

Homework & bonus points rules
Slides from Meetings / lectures: https://canvas.kth.se/groups/338172/files/folder/lecture_notes
Zoom link for lectures: See first canvas announcement in the course.
Active learning workspace (ALW)

Course specific Julia instructions: Julia instructions
Exam information: Exam information
Homework files: https://canvas.kth.se/courses/59848/files or https://canvas.kth.se/courses/57245/files

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

Can I use generative AI?

See the rules for this course:

https://canvas.kth.se/courses/57245/pages/allowed-only-in-specific-assignments

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, AL22 1-7. (abbreviations and links at the bottom of this page)
Meeting 2: Lecture
- Reading: block1.pdf: §1.1,§1.3
- Contents: Inv. it + RQI + RR
- Recommended exercises: ALW20: 1-17, 1-2, 1-26 (julia only), ALW19: 1-2
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. The Bauer-Fike theorem
Week 1: Quiz 5. Introduction to the active learning workspace environment (optional)

Week 45

Meeting 3: Lecture
- Reading: block1.pdf: §1.2,§1.3
- Contents: CGS + RGS + MGS, AF +AM.
- Recommended exercises: ALW20 1-10, 1-38, 1-21, 1-34, ALW21: 1-9
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
Week 2: Quiz 1: Lanczos method derivation
Week 2: Quiz 2: Breakdown in Arnold's method
Week 2: Quiz 3: Shift-and-invert Arnoldi method
Week 2: Quiz 4: Block 2 application: CPU-socket

Week 46

Deadline HW 1

Meeting 5: 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 6: 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 7: 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

Week 48

Deadline HW 2
Meeting 10: Lecture
- Reading: block3.pdf: §3.2.2
- Contents: QR-method: Phase 1 + Phase 2
- Recommended exercises: AL21: 3-19, 3-8,
Meeting 11: 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-4: skip
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 12: Lecture
- Reading: block4.pdf: §4.1-§4.2
- Contents: Matrix functions + Matrix exponention (scaling-and-squaring)
- Recommended exercises: AL18: 4-18, 4-23, AL21: 4-22, 4-30
Meeting 13: Lecture
- Reading: block4.pdf: §4.3
- Contents: sqrtm + Mat sign. 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)
Week 6 quiz 3: Estrada index (TODO)