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 Anna Broms. For homework explanations / questions, please contact primarily Anna.
Course literature
Block 1:
Block 2:
Block 3:
Block 4:
Block 5: (Only for PhD students taking SF3580)
See also background.pdf
Course information
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 Links to an external site.
- ALW block 1 Links to an external site.
- ALW block 2 Links to an external site.
- ALW block 3 Links to an external site.
- ALW block 4 Links to an external site.
- ALW block 5 Links to an external site.
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 (scaling-and-squaring)
- Recommended exercises: AL18: 4-18, 4-23, AL21: 4-22, 4-30
- Meeting 14: 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)
Week 50
- Meeting 15: World café workshop: Block 3-4
- Deadline HW 3
Abbreviations:
block1.pdf: block1.pdf Download block1.pdf
block2.pdf: block2.pdf Download block2.pdf
block3.pdf: block3.pdf Download block3.pdf
block4.pdf: block4.pdf Download block4.pdf
t.b.a=to be announced (will be added later)
ALWXX = ALXX = Active learning workspace corresponding to year 20XX.
AL20 = Selected problems from Active learning workspace 2020 Download Selected problems from Active learning workspace 2020 (all problems / solutions: full ALW20 Links to an external site.)
AL19 = Selected problems from Active learning workspace 2019 Download Selected problems from Active learning workspace 2019
AL18 = Selected problems from Active learning workspace 2018 Download Selected problems from Active learning workspace 2018
AL17 = Selected problems from Active learning workspace 2017 Download Selected problems from Active learning workspace 2017
AL16 = Selected problems from Active learning workspace 2016 Download Selected problems from Active learning workspace 2016
Programming language for the homeworks in this course.
- SF2524: Matlab Links to an external site. or Julia Links to an external site.
- SF3580: Julia Links to an external site.
Julia specific information for this course: Julia instructions