This course is not streamed, nor video-recorded. Old recordings do not exist. Assessment includes handing in two recorded presentations. Participation at location is much recommended!
Required prior knowledge
Contrary to the recommended prior knowledge listed below, none of the below will be reviewed. Students are expected to be able to work with them fluently.
(1) Linear algebra
- linear maps, basis transformations, row-, column, and null spaces;
- inner product spaces, orthogonal projections, orthonormalization;
- eigenvalues and -vectors, similarity transformations, spectral theorems.
(2) Abstract algebra
- group axioms, groups, matrix groups;
- general linear group, its subgroups of triangular and diagonal matrices;
- orthogonal and unitary groups.
(3) Programming
- loops and conditionals; functions, subroutines; recursion;
- finite precision arithmetic.
Recommended prior knowledge
Many of the below topics will be reviewed during the course. However, this will be done at a pace that requires prior familiarity.
(1) Matrix factorizations:
- QR, LU, and Cholesky factorization;
- Schur factorization AU = UT: unitary similarity to triangular form;
- Hessenberg reduction AU = UH: unitary similarity to upper Hessenberg form;
- Polar Factorization AU = UP: unitary similarity to SPD form.
(2) Unitary transformations (generators):
- (n-1)-hyperplane reflections;
- 2-planar rotations.
(3) Related to numerical issues:
- backward stability of an algorithm;
- conditioning of a mathematical problem;
- polynomial approximation theory.
All required and recommended prior knowledge can be found in:
[1] G.W. Strang (2023). Introduction to Linear Algebra (sixth edition). Wellesley- Cambridge Press, USA.
[2] L.N. Trefethen and D. Bau (2022) (25th anniversary edition). Numerical Linear Algebra, SIAM Society for Industrial and Applied Mathematics.
Aim of the course
The single ultimate learning goal is to advance the knowledge, to broaden the toolbox, and to increase the fluency in linear algebra of a first-year Master student in Mathematics.
Linear algebra is fundamental, and acknowledged as such by all universities offering a Bachelor in Mathematics by scheduling it immediately in the first semester. The drawback of this (logical) choice is that often, students are not yet fully equipped to appreciate and internalize the topics and to rise above the subject. This course is therefore an attempt to review and expand linear algebraic knowledge to bring it to Master level, in addition to the often merely computational abilities that stick out in that first Bachelor year.
Intended audience and description
This course aims to advance the knowledge, to broaden the toolbox, and to increase the fluency in linear algebra of a first-year Master student in Mathematics. Although thematically directed towards students interested in its numerical aspects, the course may also benefit those whose interest in advanced linear algebra is for instance derived from quantum computing, or from linear or semidefinite optimization.
The course puts familiar linear algebraic tools into context while providing new ones, against the motivational background of methods that aim to compute approximations of linear algebraic problems, as opposed to exact solutions. Such approximations are unavoidable if matrices involved are extremely large, but these are not the only situations in which approximations are required.
A central recurring theme is the design of algorithms that use isometric operations to reach their goals. The numerical perspective is that this enhances stability, as isometries do not blow up perturbations. From a more abstract point of view, such operations provide generators of the orthogonal and unitary groups and lead to insights such as the Cartan-Dieudonné Theorem for automorphism groups. Thus, numerical motives serve to explain abstract theorems in algebra.
The central themes for the course are methods to approximate solutions of linear systems and eigenvalue problems. Such methods will be studied from their mathematical foundations to the final code. This is a lengthy process, hence the number of methods studied is modest. The goal is not so much the algorithm, but the linear algebraic tools that make such methods possible.
Keywords
Orthonormality; Biorthonormality; Matrix Groups and Decompositions; Hessenberg Reduction, Implicit Q-theorem, QR-iteration; Krylov spaces; (Bi)CG and GMRES; Lanczos and Implicitly Restarted Arnoldi; Faber-Manteuffel Theorem; Interlace Theorem and Perturbation Theory (Weyl, Bauer-Fike, Cato-Temple, Gershgorin).
Assessment
The final grade is composed from the following components:
- [70%] the final exam (minimal grade of 5/10 required).
- [15%] assignment 1;
- [15%] assignment 2.
Weekly exercises are provided and will be discussed, but do not contribute to the final grade. The final exam is invigilated, written, individual, and tests whether student is able to prove theorems, by either reproducing proofs of theorems seen in class, or new results from scratch. It can also test topics from both assignments, as an additional check if student contributed to those assignments in the way that was required.
Both assignments consist of a video to be handed in, in which student (possibly with at most one fellow student) explains and demonstrates self-written computer codes, runs them live, comments on the results they produce, and answers theoretical background questions formulated in the assignment text. The focus is not on programming, but on showing understanding of the coded methods and of the workings of the algorithms implemented. The duration of such a video is typically 20-25 minutes, and can for instance be made by recording a Zoom session with screen sharing to show codes, slides.
There are no minimal requirements for the assignments.
If student participates in the resit for the exam, the grade for the resit will replace the grade of the exam and will thus count for 70% towards the final grade.
There are no replacement assignments, apart from the exceptional case that the Study Adviser of the student makes a request, in case personal circumstances made it impossible for student to meet the assignment's deadline, but only if this is necessary to pass the course (not to improve an already sufficient final grade). In such cases, the request from student's Study Adviser should arrive before the deadline, and any replacement for the assignment will only be given after the resit of the exam.
Course material
- weekly slides of the lectures;
- weekly exercise sets (2-4p) that include short summaries and motivation;
- the assignment texts (12-15p);
- condensed flyers (1-p) on recurring linear algebraic themes.
Background
Assignments in video-format have been used by the lecturer since the corona-semester of autumn 2020. Especially in the more recent context of AI-use by students for tasks that they are supposed to do themselves, this method requires students at least to speak out loud a coherent narrative while running codes and demonstrating results. This is still not AI-proof (it also need not be, as the exam is still 70% verifiably individual) but more so than asking students to simply send a pdf and codes.
Schedule
- week 01-05: 2x45 lecture and 1x45 exercise class;
- week 06: practical session, supervised work on Assignment 1;
- week 07-11: 2x45 lecture and 1x45 exercise class;
- week 12: practical session, supervised work on Assignment 2;
- week 13-16: 2x45 lecture and 1x45 exercise class
- Docent: Jan Brandts