betaFeedback

WorksMathematics

Advanced Linear Algebra with Applications - Part I (Numerical linear algebra for PDEs, machine learning, and data assimilation)

Abstract

These lecture notes form the first part of a master's-level course on advanced numerical linear algebra. Their aim is not only to present the classical algorithms, but to show why the subject has become considerably more central than it was a generation ago. Numerical linear algebra grew up alongside the numerical solution of partial differential equations, and for a long time that is where its large sparse systems came from. Ranking the nodes of a network, assimilating observations into a weather forecast, and fitting a model to a large noisy data set now lead to problems of the same kind: too large to factorise, structured, and accessible only through matrix-vector products. Strikingly few ideas are needed for all of them. Each chapter therefore develops a standard topic and then puts it to work outside its original setting. We treat norms, factorisations, conditioning and floating-point arithmetic; sparse matrices arising from finite differences, from graphs and from machine learning; stationary iterations and the smoothing property; the conjugate gradient and Lanczos methods, with spectral clustering and regularisation by early stopping; Arnoldi and GMRES, with PageRank and large least squares; and finally preconditioning, Schwarz domain decomposition and multigrid. We assume a first course in linear algebra. Every section closes with a summary of what should be retained and every chapter with exercises, several drawn from past examinations. Accompanying Python code reproduces the numerical illustrations.

Part I

Numerical linear algebra for PDEs, machine learning, and data assimilation

Lecture notes

Preface

These notes form the first part of a longer course on advanced numerical linear algebra, taught at master’s level. Their purpose is not only to present the classical algorithms, but to show why the subject has become considerably more central than it was a generation ago.

Numerical linear algebra grew up alongside the numerical solution of partial differential equations, and for a long time that was where its large sparse systems came from. This is no longer the whole story. Ranking the nodes of a network, assimilating observations into a weather forecast, and fitting a model to a large noisy data set all lead to problems of exactly the same kind: too large to factorise, structured, and accessible only through matrix–vector products. Strikingly few ideas are needed for all of them. Sparsity, the spectrum, Krylov subspaces and preconditioning recur throughout, and a method designed for a discretised Laplacian is usually the right method for a graph Laplacian or a design matrix as well.

The chapters that follow are organised around that observation. Each develops a classical topic and then puts it to work outside its original setting: sparse matrices from finite differences, graphs and machine learning; stationary iterations and the smoothing property; conjugate gradient and Lanczos, with spectral clustering and regularisation by early stopping; Arnoldi and GMRES, with PageRank and large least squares; and finally preconditioning, domain decomposition and multigrid.

This first part is deliberately foundational: factorisations and conditioning, iterative methods, Krylov subspaces and preconditioners are what the second part of the course, not reproduced in this volume, takes for granted throughout.

The level is that of a first-year master’s student in mathematics, computer science or a computational discipline. We assume a first course in linear algebra and some familiarity with numerical analysis, and we prove what can be proved compactly, leaving the more technical results to the literature. Every section closes with a summary of what should be retained, and every chapter with exercises, several taken from past examinations.

Reading about an iterative method is, however, a poor substitute for watching one converge. The illustrations in these notes are reproducible, and we encourage readers to run and modify the accompanying Python code, available at https://github.com/vicdolean/scicomp_examples: changing a parameter, a matrix or a stopping criterion is by far the fastest way to develop a feeling for when these methods work and when they do not.

We are grateful to Rafał Wrona (Independent Researcher, Kraków, Poland), whose careful reading and explicit counterexamples led us to correct a number of errors, mainly in Chapter 3.

A note on the use of AI tools. The structure of these notes, the choice and ordering of the topics, and the mathematical content are the authors’ own. Some of the material is standard and presented here in our own way; some of it is drawn from research we ourselves engaged in. In preparing the manuscript we used a generative AI assistant to help identify the seminal references on a given topic, to improve the language, and to improve the graphical content. All statements, proofs and references have been checked by the authors, who take full responsibility for the contents.

Victorita Dolean and Jemima M. Tabeart Eindhoven, October 20, 2026

Solving Linear Systems: A Unified Foundation

Overview

Linear algebra forms the backbone of many modern scientific and engineering computations. From solving systems of equations in structural analysis, optimizing models in machine learning, and forecasting weather through data assimilation, linear algebraic methods are pervasive. However, in practical computations, the mathematical representations of real numbers must confront the limitations of computer arithmetic. Floating-point numbers can only approximate real numbers, leading to small but inevitable rounding errors, and even mathematically exact operations can be extremely sensitive to those tiny errors depending on the structure of AA.

This chapter lays the numerical foundations used throughout the rest of the course: how to measure the size of vectors, matrices, and errors (norms); how a problem’s own sensitivity to perturbations is quantified (conditioning); how floating-point arithmetic and algorithms can amplify or control error (stability); and the two standard families of solvers for Ax=bAx=b — direct factorizations (LU, Cholesky) and stationary iterative methods (Jacobi, Gauss–Seidel, SOR, Richardson).

The Scale of Linear Algebra in Real Life
Weather forecasts use systems with 10910^9 unknowns – solving linear systems is essential every few hours, and must be done in minutes.
Google’s PageRank was originally computed by solving a giant eigenvalue problem.
Deep Learning has a lot of linear algebra: backpropagation is mostly matrix multiplies and chain-rule gradients.

Table 2.

By the end of this chapter, you should be able to:

  • Define and compute common vector and matrix norms, and explain why all norms are equivalent in finite dimension.

  • Relate eigenvalues, eigendecompositions, the Schur decomposition, and the SVD to the spectral radius and to matrix norms.

  • Explain the sources of floating-point error (rounding, truncation, cancellation) and use the condition number κ(A)\kappa(A) to relate backward and forward error.

  • Compute the LULU and Cholesky factorizations of a matrix, and state why partial pivoting is needed for backward stability.

  • Derive the Jacobi, Gauss–Seidel, SOR, and Richardson iterations from a matrix splitting A=M−NA=M-N, and state the convergence criterion ρ(G)<1\rho(G)<1.

Norms and Matrix Decompositions

The first electronic computer, ENIAC (1940s), already faced severe rounding problems. Engineers had to carefully redesign algorithms to avoid divergence even after a few thousand operations.

Vector and Matrix Norms

Definition 1.1.1 (Vector norms). Given a vector x∈Rnx\in\mathbb{R}^{n}, the common norms are:

  • ℓ1\ell^{1} norm: ∥x∥1=∑i=1n∣xi∣\lVert x\rVert_{1}=\sum_{i=1}^{n}|x_{i}|

  • ℓ2\ell^{2} norm (Euclidean): ∥x∥2=(∑i=1n∣xi∣2)1/2\lVert x\rVert_{2}=\left(\sum_{i=1}^{n}|x_{i}|^{2}\right)^{1/2}

  • ℓ∞\ell^{\infty} norm: ∥x∥∞=max⁡i∣xi∣\lVert x\rVert_{\infty}=\max_{i}|x_{i}|

These norms satisfy the following properties:

  • Non-negativity: ∥x∥≥0\lVert x\rVert\geq0 and ∥x∥=0\lVert x\rVert=0 if and only if x=0x=0

  • Homogeneity: ∥αx∥=∣α∣∥x∥\lVert\alpha x\rVert=|\alpha|\lVert x\rVert for any scalar α\alpha

  • Triangle inequality: ∥x+y∥≤∥x∥+∥y∥\lVert x+y\rVert\leq\lVert x\rVert+\lVert y\rVert

Norms give us a way to measure the size (or length) of a vector. They are particularly useful in determining convergence of sequences, measuring distances between vectors, and quantifying approximation errors.

Proposition 1.1.2 (Norm equivalence). All norms on a finite-dimensional vector space are equivalent. This means that for any two norms ∥⋅∥a\lVert\cdot\rVert_{a} and ∥⋅∥b\lVert\cdot\rVert_{b}, there exist constants c1,c2>0c_{1},c_{2}>0 such that:

c1∥x∥a≤∥x∥b≤c2∥x∥afor all x∈Rn.c_{1}\lVert x\rVert_{a}\leq\lVert x\rVert_{b}\leq c_{2}\lVert x\rVert_{a}\qquad\text{for all }x\in\mathbb{R}^{n}.

Thus, different norms can be used interchangeably when analyzing asymptotic behavior, even though their numerical values may differ. For instance, ∥x∥∞≤∥x∥2≤n∥x∥∞\lVert x\rVert_{\infty}\leq\lVert x\rVert_{2}\leq\sqrt{n}\lVert x\rVert_{\infty} and ∥x∥2≤∥x∥1≤n∥x∥2\lVert x\rVert_{2}\leq\lVert x\rVert_{1}\leq\sqrt{n}\lVert x\rVert_{2}, so here c1=1c_{1}=1 and c2=nc_{2}=\sqrt{n} (see Problem 2).

Unit balls for the $\ell^1$, $\ell^2$, and $\ell^\infty$ norms

Figure 1.1. Unit balls {x:∥x∥=1}\{x : \lVert x\rVert= 1\} for the ℓ1\ell^1, ℓ2\ell^2, and ℓ∞\ell^\infty norms in R2\mathbb{R}^2: the same vector has a different "size" depending on which norm is used.

Eigenvalues and Matrix Decompositions

Before turning to matrix norms, it is useful to recall the key spectral objects that will reappear throughout the course: eigenvalues, and the two canonical matrix factorizations built from them.

Definition 1.1.3 (Eigenvalues, eigendecomposition, spectral radius). A scalar λ∈C\lambda\in\mathbb{C} and nonzero vector xx satisfying Ax=λxAx = \lambda x are an eigenvalue and eigenvector of AA. If A∈Rn×nA \in\mathbb{R}^{n \times n} is diagonalizable, it admits an eigendecomposition

A=VΛV−1,Λ=diag⁡(λ1,…,λn),A = V\Lambda V^{-1}, \qquad\Lambda= \operatorname{diag}(\lambda_1,\ldots,\lambda_n),

where the columns of VV are eigenvectors. The spectral radius is ρ(A)=max⁡i∣λi∣\rho(A) = \max_i |\lambda_i|.

Definition 1.1.4 (Schur decomposition and SVD). Every A∈Cn×nA \in\mathbb{C}^{n \times n} admits a Schur decomposition A=QTQ∗A = QTQ^* with QQ unitary (Q∗Q=QQ∗=IQ^*Q = QQ^* = I) and TT upper triangular, with the eigenvalues of AA on the diagonal of TT. Every A∈Rm×nA \in\mathbb{R}^{m \times n} (or Cm×n\mathbb{C}^{m \times n}) admits a singular value decomposition (SVD) A=UΣV∗A = U\Sigma V^* with U,VU,V unitary and Σ=diag⁡(σ1,…)\Sigma= \operatorname{diag}(\sigma_1,\ldots) where σi≥0\sigma_i \ge0.

Remark 1.1.5. Every symmetric matrix is diagonalizable with real eigenvalues; if it is also symmetric positive definite (SPD), i.e. xTAx≥0x^\mathsf{T}Ax \ge0 with equality only for x=0x = 0, its eigenvalues are strictly positive. Unlike the eigendecomposition, the Schur decomposition and the SVD exist for every matrix, which is why they underpin general-purpose numerical algorithms.

Takeaways Eigenvalues and the spectral radius ρ(A)\rho(A) control the long-run behaviour of iterative processes (§ 2.5); the Schur decomposition and the SVD are the two factorizations that always exist and that later chapters (and the induced 2-norm below) build on.

Matrix Norms

Matrix norms are critical for analyzing the stability and conditioning of algorithms and problems involving linear systems, eigenvalue computations, and optimization. Matrix norms are often induced by vector norms.

Definition 1.1.6 (Induced norm (operator norm)). For a matrix A∈Rm×nA \in\mathbb{R}^{m \times n} the induced norm (operator norm) is defined by

∥A∥=sup⁡x≠0∥Ax∥∥x∥=max⁡∥x∥=1∥Ax∥\lVert A\rVert= \sup_{x \ne0} \frac{\lVert Ax\rVert}{\lVert x\rVert} = \max_{\lVert x\rVert=1} \lVert Ax\rVert

The three induced norms used throughout these notes are the following.

  • Spectral norm (2-norm): ∥A∥2=σmax⁡(A)\lVert A\rVert_2 = \sigma_{\max}(A), where σmax⁡\sigma_{\max} is the largest singular value.

  • 1-norm ∥A∥1\lVert A\rVert_1: maximum absolute column sum

  • Infinity-norm ∥A∥∞\lVert A\rVert_\infty: maximum absolute row sum

Not every matrix norm is induced by a vector norm. The most important exception is the Frobenius norm,

∥A∥F=(∑i=1m∑j=1n∣aij∣2)1/2\lVert A\rVert_F = \left(\sum_{i=1}^{m}\sum_{j=1}^{n} \lvert a_{ij}\rvert^2\right)^{1/2}

It is exactly the ℓ2\ell^2 norm of the matrix viewed as a vector of its entries.

Proposition 1.1.7 (Note on induced norms). For an induced matrix norm ∥A∥\lVert A\rVert, we have:

  • ∥AB∥≤∥A∥⋅∥B∥\lVert AB\rVert\le\lVert A\rVert\cdot\lVert B\rVert

  • ∥A∥≥∥Ax∥/∥x∥\lVert A\rVert\ge\lVert Ax\rVert/\lVert x\rVert for all x≠0x \ne0

This submultiplicative property makes induced norms useful in bounding errors and proving convergence.

Takeaways

On finite-dimensional spaces all norms are equivalent: asymptotically they give the same notion of convergence, but numerically their values can differ significantly.

Floating-Point Arithmetic, Error, Conditioning, and Factorizations

Floating-Point Arithmetic

The Ariane 5 rocket self-destructed (1996) due to a floating-point overflow error when converting a 64-bit number to a 16-bit integer. This incident underscores the risks inherent in floating-point arithmetic and careless type conversions.

Floating-point arithmetic is governed by the IEEE 754 standard [25], which fixes both the set of representable numbers and the way operations on them are rounded.

Definition 1.2.1 (Binary floating-point numbers). Fix a precision pp and an exponent range [emin⁡,emax⁡][e_{\min}, e_{\max}]. A normal floating-point number is

x=(−1)S(1.m1m2⋯mp−1)22e,(1.m1⋯mp−1)2=1+∑k=1p−1mk2−k∈[1,2),x = (-1)^S (1.m_1m_2 \cdots m_{p-1})_2 2^e,\qquad(1.m_1 \cdots m_{p-1})_2 = 1 + \sum_{k=1}^{p-1} m_k 2^{-k} \in[1,2),

with sign S∈{0,1}S \in\{0,1\}, bits mk∈{0,1}m_k \in\{0,1\} and emin⁡≤e≤emax⁡e_{\min} \le e \le e_{\max}.

The leading 1 is not stored, so pp bits of precision cost p−1p-1 bits of storage. The exponent is held as an unsigned E=e+biasE=e+\text{bias}, bias=2k−1−1\text{bias}=2^{k-1}-1 for kk exponent bits; the two extreme EE are reserved, one for zero and the subnormals (leading digit 0, filling the gap around zero), the other for ±∞\pm\infty and NaN. For instance −6.5=−(1.101)22-6.5=-(1.101)_2^2. S=1S=1, m=1010…0m=1010\ldots0, e=2e=2.

The first IEEE standard was introduced in 1985. For a long time single (8 exponent bits and 23-bits for the significand) and double precision (11 exponent bits and 52 significand bits) were the most commonly-used formats. However, in recent years there has been a growth in interest in reduced precisions, such as half precision (5 exponent bits and 10 significand bits), non-standard precisions such as bfloat16 (8 exponent bits and 7 significand bits) and proprietary formats like Nvidia’s TensorFloat-32 (8 exponent bits and 10 significand bits). Much of this development has been driven by machine learning applications, and the desire to accelerate performance. In data assimilation, the computational cost is dominated by evaluations of the PDE model, so large gains can be made by applying the model in single precision [20].

One option is to run an entire algorithm in a reduced precision, which will lead to increased computational efficiency, but may result in degraded performance. This has motivated ‘mixed-precision’ approaches, particularly in the numerical linear algebra community, where different steps of an algorithm are run in different precisions. Such approaches aim to combine the computational benefits of reduced precision, while ensuring rapid convergence and computational stability (see e.g. [24] [1] for comprehensive reviews).

The Gap Between Neighbouring Floats Floating-point numbers are not spread evenly along the real line. Between 2e2^e and 2e+12^{e+1}, with ee the exponent of Definition 1.2.1, they are evenly spaced 2e−(p−1)2^{e-(p-1)} apart, since the significand advances one bit at a time. Because ∣x∣\lvert x\rvert lies in that range, the spacing near xx or its gap, is

gap⁡(x)≈∣x∣⋅2−(p−1),\operatorname{gap}(x) \approx\lvert x\rvert\cdot2^{-(p-1)},

proportional to the magnitude: doubling xx doubles it. In double precision the gap just above 1 is 2−52≈2.2×10−162^{-52}\approx2.2\times10^{-16}; near 101610^{16} it is 2, so the representable numbers there run …,1016,1016+2,…\ldots,10^{16},10^{16}+2,\ldots with nothing in between, and 1016+110^{16}+1 falls exactly halfway between two neighbours.

Unit Roundoff Rounding to the nearest moves xx by at most half a gap, that is by at most ∣x∣⋅2−p\lvert x\rvert\cdot2^{-p}. Dividing by ∣x∣\lvert x\rvert, the relative error is at most 2−p2^{-p} regardless of the magnitude of xx.

References

  1. [14]Anne Greenbaum. Iterative Methods for Solving Linear Systems. SIAM, Philadelphia, PA, 1997.DOI
  2. [15]Anne Greenbaum, Vlastimil Pták, and Zdenvěk Strakoš. Any Nonincreasing Convergence Curve is Possible for GMRES. SIAM Journal on Matrix Analysis and Applications, 17(3):465–469, July 1996.DOI
  3. [16]S. A. Haben. Conditioning and Preconditioning of the Minimisation Problem in Variational Data Assimilation. PhD thesis, Department of Mathematics and Statistics, University of Reading, 2011.DOI
  4. [17]Wolfgang Hackbusch. Multi-Grid Methods and Applications, volume 4 of Springer Series in Computational Mathematics. Springer, Berlin, 1985.DOI
  5. [18]Martin Hanke. Conjugate Gradient Type Methods for Ill-Posed Problems, volume 327 of Pitman Research Notes in Mathematics Series. Longman Scientific & Technical, Harlow, 1995. Reissued by Chapman & Hall/CRC, Boca Raton, 2018.
  6. [19]Per Christian Hansen. Rank-Deficient and Discrete Ill-Posed Problems: Numerical Aspects of Linear Inversion. SIAM, Philadelphia, PA, 1998.
  7. [20]Sam Hatfield, Andrew McRae, Tim Palmer, and Peter Düben. Single-Precision in the Tangent-Linear and Adjoint Models of Incremental 4D-Var. Monthly Weather Review, 148(4):1541–1552, April 2020.DOI
  8. [21]Taher H. Haveliwala and Sepandar D. Kamvar. The second eigenvalue of the Google matrix. Technical Report 2003-20, Stanford University, 2003.
  9. [22]Magnus R. Hestenes and Eduard Stiefel. Methods of conjugate gradients for solving linear systems. Journal of Research of the National Bureau of Standards, 49(6):409–436, 1952.DOI
  10. [23]Nicholas J. Higham. Accuracy and Stability of Numerical Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA, 2 edition, 2002.
  11. [24]Nicholas J. Higham and Theo Mary. Mixed precision algorithms in numerical linear algebra. Acta Numerica, 31:347–414, May 2022.DOI
  12. [25]IEEE. IEEE standard for floating-point arithmetic. IEEE Std 754-2019 (Revision of IEEE 754-2008), 2019.
  13. [26]Cornelius Lanczos. An iteration method for the solution of the eigenvalue problem of linear differential and integral operators. Journal of Research of the National Bureau of Standards, 45(4):255–282, 1950.DOI
  14. [27]Amy N. Langville and Carl D. Meyer. Google’s PageRank and Beyond: The Science of Search Engine Rankings. Princeton University Press, Princeton, NJ, 2006.
  15. [28]M. J. Martin, A. Hines, and M. J. Bell. Data assimilation in the FOAM operational short-range ocean forecasting system: A description of the scheme and its impact. Quarterly Journal of the Royal Meteorological Society, 133(625):981–995, 2007.DOI
  16. [29]J. A. Meijerink and H. A. van der Vorst. An iterative solution method for linear systems of which the coefficient matrix is a symmetric M-matrix. Mathematics of Computation, 31(137):148–162, 1977.DOI
  17. [30]Jean-Michel Muller, Nicolas Brunie, Florent de Dinechin, Claude-Pierre Jeannerod, Mioara Joldeş, Vincent Lefèvre, Guillaume Melquiond, Nathalie Revol, and Serge Torres. Handbook of Floating-Point Arithmetic. Birkhäuser, Cham, 2 edition, 2018.
  18. [31]Yurii Nesterov. Introductory Lectures on Convex Optimization: A Basic Course. Springer, Boston, MA, 2004.
  19. [32]Alexander M Ostrowski. On the linear iteration procedures for symmetric matrices. Rend. Mat. Appl., 14:140–163, 1954.
  20. [33]Michael L. Overton. Numerical Computing with IEEE Floating Point Arithmetic. Society for Industrial and Applied Mathematics, Philadelphia, PA, 2 edition, 2025.
  21. [34]Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The PageRank citation ranking: Bringing order to the web. Technical Report 1999-66, Stanford InfoLab, 1999.
  22. [35]Christopher C. Paige. Accuracy and effectiveness of the Lanczos algorithm for the symmetric eigenproblem. Linear Algebra and its Applications, 34:235–258, 1980.DOI
  23. [36]Nasim Rahaman, Aristide Baratin, Devansh Arpit, Felix Draxler, Min Lin, Fred Hamprecht, Yoshua Bengio, and Aaron Courville. On the Spectral Bias of Neural Networks. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of PMLR, pages 5301–5310, 2019.arxiv.org/abs/1806.08734
  24. [37]Yousef Saad. On the rates of convergence of the Lanczos and the block-Lanczos methods. SIAM Journal on Numerical Analysis, 17(5):687–706, 1980.DOI
  25. [38]Yousef Saad. Iterative Methods for Sparse Linear Systems. SIAM, Philadelphia, PA, 2nd edition, 2003.DOI
  26. [39]Yousef Saad and Martin H. Schultz. GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM Journal on Scientific and Statistical Computing, 7(3):856–869, 1986.
  27. [40]Andrea Toselli and Olof Widlund. Domain Decomposition Methods: Algorithms and Theory, volume 34 of Springer Series in Computational Mathematics. Springer, Berlin, 2005.DOI
  28. [41]Lloyd N. Trefethen and Mark Embree. Spectra and Pseudospectra: The Behavior of Nonnormal Matrices and Operators. Princeton University Press, Princeton, NJ, 2005.
  29. [42]Richard S. Varga. Matrix Iterative Analysis. Springer, Berlin, Heidelberg, 2nd edition, 2000.
  30. [43]Ulrike von Luxburg. A tutorial on spectral clustering. Statistics and Computing, 17(4):395–416, 2007.arxiv.org/abs/0711.0189
  31. [44]Andrew J. Wathen. Preconditioning. Acta Numerica, 24:329–376, 2015.DOI
  32. [45]J. H. Wilkinson. The Algebraic Eigenvalue Problem. Clarendon Press, 1965.
  33. [46]David Young. On Richardson’s Method for Solving Linear Systems with Positive Definite Matrices. Journal of Mathematics and Physics, 32(1-4):243–255, 1953.DOI
  34. [47]David M. Young. Convergence properties of the symmetric and unsymmetric successive overrelaxation methods and related methods. Mathematics of Computation, 24(112):793–807, 1970.

Paper details

vlnc:W_c8x26dpg
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 13

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents