One of the most important applications of numerical linear algebra is to the solution or approximate solution of a linear system of equations Ax=b. When the linear system in question arises due to the discretisation of a partial differential equation (PDE) or a coupled system of PDEs, then the system matrix inherits many features from the underlying PDE operator and the chosen discretisation scheme. Solving such linear systems using naive elimination methods can require significant computational resources and could involve many hours/days of run time. Obtaining real time solutions on desktop or laptop computers is simply not possible in many applications without an optimised and tailor-made solver.
For very large problems, involving millions of equations, iterative schemes such as Krylov subspace methods are the only viable approach. A draw-back is that convergence rates depend on the condition number and structure of the system matrix. These are heavily influenced by the properties of the underlying PDE operators. Preconditioning is required. A preconditioner, in its simplest guise, is a matrix P that mimics the properties of the inverse of the original system matrix, but for which it is cheap to compute the matrix-vector product y=Pb. Designing optimal preconditioners is a crucial step. Whilst some PDE operators such as the Laplacian are relatively 'nice', others (such as operators associated with the H(div) and H(curl) function spaces), are much more challenging.
In Manchester, we are currently carrying out research into a range of iterative methods and preconditioning techniques for solving PDEs that arise in diverse applications such as fluid flow modelling and electromagnetics. We have extensive experience in solving very large, sparse systems of equations that arise in finite element computations and particular expertise in solving saddle-point problems that arise in solving problems with constraints.
We are currently investigating robust solvers and preconditioners for PDEs with uncertain coefficients (for more details see uncertainty quantification). Stochastic finite element methods (SFEMs) lead to linear systems that are orders of magnituge larger than for deterministic problems. The picture shows two spy plots of SFEM matrices. Each square represents another matrix, whose dimensions can be in the order of many hundreds of thousands.