The course treats a selection of numerical algorithms from linear algebra, PDEs and optimization. Each algorithm has had a major impact on the development of computational mathematics and is in constant use in numerical modelling. In addition to the algorithm itself, we present its theoretical basis and context, including typical applications. The course includes a hands-on computing component.
Week 1: Conjugate gradients (Bill McLean)
This is a class of methods for solving symmetric positive definite linear systems, and is particularly suited to the large, sparse systems arising from discretizations of self-adjoint elliptic boundary value problems. In addition to the congjugate gradient (CG) method, we discuss briefly the wider class of Krylov subspace methods, especially generalized minimum residuals (GMRES).
Week 2: Domain decomposition (Thanh Tran)
The numerical solution of boundary value problems often leads to algebraic systems which can be solved by the CG method. For problems with practical interest, these systems are usually of such a large scale that they require substantial attention to improve the solution process and reduce computational time. Domain decomposition is a relatively new field which can be used to devise fast and parallel algorithms.
Week 3: Interior point methods and semidefinite programming (Rob Womersley)
Linear programming, an optimization problem in which the objective function and all the constraints are affine functions of the variables, has been widely solved by the simplex method which moves between adjacent vertices of the feasible region. Invented by Dantzig in 1947, the simplex method is not a polynomial time algorithm, although it worked well in practice. In 1984 Karmarkar published a fast polynomial-time interior method for linear programming, which was soon related to previously known barrier methods. This started a revolution in both the theory and practice of constrained optimization, to the stage where interior point methods are now standard. This allows practical solution of classes of problems, such as semi-definite programing in which the variables are symmetric positive semi-definite (covariance) matrices, which were previously regarded as intractable.
Week 4: QR algorithm (Bill McLean)
This is a technique for computing the eigenvalues and eigenvectors of a square matrix, and also has an interesting connection with Gauss quadrature. A key ingredient is the QR factorization, which in effect generates an orthonormal basis for the column space of the given matrix, and has a variety of other important uses in numerical linear algebra. For simplicity, we mostly restrict our attention to symmetric eigenproblems.
28 hours of hours spread over four weeks, plus consultation as required.
The course assumes a solid background in linear algebra and multivariable calculus. Topics 1 and 2 assume some familiarity with partial differential equations. For the practical computing component, you should have some experience with basic procedural programming in an appropriate language, such as Matlab or Python.
- A. Toselli and O. Widlund, Domain Decomposition Methods - Algorithms and Theory, Spinger-Verlag, Berlin 2005
- B. Smith, P. Bjorstad, and W. Gropp, Domain Decomposition - Parallel Multilevel Methods for Elliptic Partial Differential Equations, Cambridge University Press, 1996
- A. Quarteroni and A. Valli, Domain Decomposition Methods for Partial Differential Equations, Oxford Science Publications, 1999
About Willam McLean
My research interests are in numerical analysis for partial differential equations and integral equations. In recent year, I have worked on discontinuous Galerkin methods for fractional diffusion problems, as well as Laplace transform techniques and iterative solvers.
About Robert Womserley
Robert Womersley's research interests include optimization methods and applications, computational mathematics and high performance computing and computational finance.
About Thanh Tran
Thanh Tran's research interests are in numerical analysis for determinisitic and stochastic partial differential equations, integral equations; approximation on a sphere; and fast solution techniques (domain decomposition methods).