Introduction
This is a course about Numerical Linear Algebra. Numerical Linear Algebra is the foundation of modern scientific computing and has many applications: from signal processing to computational physics and data science. The aim of this course is to give a comprehensive overview of the methods and algorithms used to solve problems such as linear systems of equations, eigenvalue problems, and matrix decompositions. I intend to cover iterative methods such as the Jacobi and Gauss-Seidel methods, as well as advanced techniques for sparse matrices, such as Krylov and multigrid methods. Furthermore, we will implement the algorithms presented in the programming language Julia.
math, 65Fxx, numerical linear algebra, julia
Why learn Numerical Linear Algebra?
Numerical linear algebra is the foundation of modern scientific computing. It deals with the numerical approximation of problems such as linear systems and eigenvalue problems. Many techniques for solving differential equations, such as the finite element method (FEM) or the finite difference method, lead to a system of linear equations; As such, numerical linear algebra has many applications: from image and signal processing to computational physics, data science and more.
About this Course
Target Audience
This course is primarily aimed at undergraduate students of mathematics, physics and engineering. However, it is also suitable for engineers who use these algorithms (linear solvers, multigrid methods) in commercial software and want to gain a deeper understanding of how they work.
Prerequisites
This is not a linear algebra course, so a solid understanding of linear algebra is required. For the implementation of the numerical algorithms, it is also useful to have some programming skills in either MATLAB, Python or Julia. However, there will be a short introduction to Julia programming at the beginning, so basic programming skills are sufficient.
Syllabus
- Week 1 – 5: Introduction to Julia
- Week 6 – 10: Algorithms for dense matrices
- Perturbation theory
- Direct solvers for linear systems
- Iterative solvers for linear systems (Gauss-Seidel)
- Calculation of Eigenvalues (power method)
- Week 11 – 26: Algorithms for sparse matrices
- Sparse LU-decompostion
- Sparse matrix ordering algorithms
- Krylow methods (CG, BiCGStab, GMRES)
- Special iteration methods (multigrid, domain decomposition)
The exact structure of this course is subject to change and may vary.
Literature
Theoretical Textbooks
The standard textbook is (Golub and Van Loan 2013); it has over 1500 citations and covers basically everything. However, it is very dense and not very pleasant to read. I would recommend it more as a reference book rather than for self study.
A good alternative is probably (Rannacher 2018), which is very readable and can be used as an introductory textbook. It is open-access.
The book (Meister 2015) is written by a former professor of mine. It is particularly interesting because it covers advanced Krylow-methods such as QMRCGSTAB and has a large chapter on Multigrid methods.
Practical Textbooks
The book (Wendland 2018) is probably the best, in my opinion; it is well structured and has a good balance between theory and application. The algorithms are given in pseudocode, which makes it easy to implement them in the programming language of your choice.
Since numerical linear algebra is a very practical subject, I think a good book should also include implementations of the actual algorithms. This is the case for (Lyche 2020), which has code in MATLAB/Octave, and for (Darve and Wootters 2021), which has implementations in Julia. The former also has a companion book containing many exercises and solutions.
Advanced Textbooks
The books (Scott and Tůma 2023) and (Hackbusch 2016) both deal with sparse matrices, but have a very different focus. While the former covers direct methods and matrix decompositions for developing algebraic preconditioners, the latter deals with advanced iterative methods for sparse systems, such as Krylov, multigrid or domain decomposition methods. There is also (Davis 2006), which is entirely about direct methods for sparse linear systems.
For Eigenvalue problems, there is (Saad 2011), which focuses on Krylov methods, but also covers modern techniques such as AMLS and the Jacobi-Davidson method. The book is accompanied by MATLAB codes, and has an interesting chapter on applications in physics.
It is probably a good idea to look at some of these books later in this course and focus on individual chapters that are of most interest.
