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

Course literature

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

See also background.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/groups/303121/files/folder/lecture_material

ALW for FSF3580 Numerical linear algebra: https://jarlebring.ddns.net/~jarl/active_learning/active_learning.php?id=11&contents=1

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, 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 + AM intro
- 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: CGS + RGS + 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
- Essentially an interactive exercise
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 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
Week 4 quiz 3: skip
Week 4 quiz 4: BiCG method derivation
Week 4 quiz 5: Simultaneous iteration part 1: Normalized and unnormalized (important for lectures next week)
Week 4 quiz 6: Simultaneous iteration part 2: Convergence of unnormalized (diagonal + triangular) (important for lectures next week)

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