This autumn I will lecture the course **MA398 Matrix Analysis and Algorithms** at the University of Warwick. The course will be an introduction to matrix analysis and to the basic algorithms of numerical linear algebra, broadly following a text by Andrew Stuart and Jochen Voss [2009 version] [2012 version]. I plan on posting summary notes to this blog, roughly in correspondence with the chapters of the Stuart & Voss text; I’ll tag them all “ma398”.

After some necessary introductory material, the course will cover three basic problems of numerical linear algebra:

**Simultaneous Linear Equations (SLE).**Given a matrix*A*∈ ℂ^{n×n}and a vector*b*∈ ℂ^{m}, find*x*∈ ℂ^{n}such that*A**x*=*b*.**(Overdetermined) Least Squares (LSQ).**Given a matrix*A*∈ ℂ^{m×n}with*m*≥*n*and a vector*b*∈ ℂ^{m}, find*x*∈ ℂ^{n}that minimises ‖*A**x*−*b*‖_{2}^{2}.**Eigenvalue/Eigenvector Problem (EVP).**Given a matrix*A*∈ ℂ^{n×n}, find (*x*,*λ*) ∈ ℂ^{n}×ℂ such that*A**x*=*λ**x*and ‖*x*‖_{2}= 1.

The common feature that I see in these three problems is that they occur naturally in many theoretical and practical settings and are mathematically very simple to describe, but actually *solving* them efficiently in practice requires some skill. In particular, these problems are all barely above high-school level for *m* = *n* = 2 or 3, but take on a rather different character when *m* and *n* are of order 10^{6}! Sometimes the problems are practical ones of time and resources, but in other cases they are more fundamental: for example, thanks to the Abel–Ruffini theorem, there can in general be no exact solution to (EVP) for *n* ≥ 5 that uses only the rational numbers and finitely many applications of the elementary arithmetical operations of +, −, ×, ÷ and √.

Some of the general tools that will be used and topics addressed in the course will include:

**Vector and Matrix Analysis.**Vector norms and inner products. Eigenvalues and eigenvectors. Dual spaces. Matrix norms. Structured matrices.**Matrix Factorizations.**Diagonalization. Jordan canonical form. Singular value decomposition. QR, LU and Cholesky factorizations.**Stability and Conditioning.**Conditioning of the SLE, LSQ and EVP problems. Stability of algorithms.**Complexity of Algorithms.**Computational cost. Matrix-matrix multiplication. Fast Fourier transform. Bidiagonal and Hessenberg forms.**SLE.**Gaussian elimination. Partial pivoting. QR factorization.**Iterative Methods.**Linear methods. Jacobi method. Gauss–Seidel and SOR methods. Nonlinear methods. Steepest descent. Conjugate gradients.**LSQ.**LSQ via normal equations, QR factorization, and SVD.**EVP.**Power method. Inverse iteration. Rayleigh quotient iteration. Simultaneous iteration. QR algorithm for eigenvalues. Divide-and-conquer for symmetric problems.