Introduction

Marcel Angenvoort

2025-01-02

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.

• Numerical linear algebra is the foundation of scientific computing
• it deals with numerical approximation of linear systems and Eigenvalue problems
• techniques for solving PDEs often lead to a system of linear equations
• many applications: signal processing, computational physics, data science, …

About this Course

Target Audience:

• Students in math/physics/engineering
• Engineers who want to gain a deeper understanding of numerical algorithms
• anyone who is interested in scientific computing

Prerequisites:

• solid knowledge of Linear Algebra
• basic programming skills (Julia/Python/MATLAB)

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)

Note

The exact structure of this course is subject to change and may vary.

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.

(Golub and Van Loan 2013)

 

(Rannacher 2018)

 

(Meister 2015)

 

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.

(Wendland 2018)

 

(Lyche 2020)

 

(Darve and Wootters 2021)

 

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.

(Scott and Tůma 2023)

 

(Hackbusch 2016)

 

(Davis 2006)

 

(Saad 2011)

References

Darve, Eric, and Mary Wootters. 2021. Numerical Linear Algebra with Julia. Philadelphia: Society for Industrial; Applied Mathematics.

Davis, Timothy A. 2006. Direct Methods for Sparse Linear Systems. SIAM.

Golub, Gene H., and Charles F. Van Loan. 2013. Matrix Computations. 4th ed. Baltimore, MD: The Johns Hopkins University Press.

Hackbusch, Wolfgang. 2016. Iterative Solution of Large Sparse Systems of Equations. 2nd ed. Springer.

Lyche, Tom. 2020. Numerical Linear Algebra and Matrix Factorizations. Cham, Switzerland: Springer.

Meister, Andreas. 2015. Numerik Linearer Gleichungssysteme. 5th ed. Springer Spektrum.

Rannacher, Rolf. 2018. Numerical Linear Algebra. Heidelberg University Publ. https://doi.org/10.17885/heiup.407.

Saad, Yousef. 2011. Numerical Methods for Large Eigenvalue Problems. 2nd ed. SIAM.

Scott, Jennifer, and Miroslav Tůma. 2023. Algorithms for Sparse Linear Systems. Cham, Switzerland: Birkhäuser. https://doi.org/10.1007/978-3-031-25820-6.

Wendland, Holger. 2018. Numerical Linear Algebra: An Introduction. Cambridge University Press.