Workshop on Linear Algebra for PDEs and Optimization, 2017

Schedule:

Titles and Abstracts:

David Silvester - Uncertainty Quantification: does it need efficient linear algebra?

This talk reviews developments in the design of robust solution methods for the Navier-Stokes equations modelling incompressible fluid flow. We focus on the Boussinesq equations in the first instance.  These equations represent a limiting case of models of fluid flow forced by gravity where the fluid velocity is much smaller than the local sound speed, and where only small temperature deviations from the average value are allowed. Such models are used in a variety of different physical applications, for example, ocean modeling, convection of the earth’s mantle and semiconductor crystal growth. 

In the second part of the talk we will show that our basic solution strategy can be readily extended to more complicated models, including steady flow problems that are stochastic in the sense that they have uncertain input data. We will show that naive Monte-Carlo algorithms offer a very inefficient way of generating solution statistics if one wants to quantify the uncertainty in a sample solution to such a flow problem.

This is joint work with Catherine Powell.

Alison Ramage - A Multilevel Preconditioner for Data Assimilation with 4D-Var

Large-scale variational data assimilation problems are commonly found in applications like numerical weather prediction and oceanographic modelling. The 4D-Var method is frequently used to calculate a forecast model trajectory that best fits the available observations to within the observational error over a period of time. One key challenge is that the state vectors used in realistic applications could contain billions or trillions of unknowns so, due to memory limitations, in practice it is often impossible to assemble, store or manipulate the matrices involved explicitly. In this talk we present a limited memory approximation to the inverse

Hessian of the linearised quadratic minimisation subproblems, computed using the Lanczos method, based on a multilevel approach. We then use this approximation as a preconditioner within 4D-Var and show that it can reduce memory requirements and increase computational

efficiency.

Julian Hall - High performance numerical linear algebra for the revised simplex method

Solving large scale sparse linear programming problems (LP) efficiently using the revised simplex method depends on the solution of sparse linear systems of equations with related coefficient matrices. Although these coefficient matrices are frequently highly reducible, making their factorization computationally straightforward, this does lead to the the phenomenon of hyper-sparsity being demonstrated for important classes of LP problems. Other classes of LP problems inherit structure from the underlying model allowing parallel computation to be exploited. This talk will describe how hyper-sparsity and problem structure may be exploited, as well as presenting novel techniques for updating the invertible representation of the coefficient matrix which underpin the computational efficiency of the open-source dual revised simplex solver, h2gmp.

Jacek Gondzio - Preconditioners for higher order methods in signal reconstruction

We address efficient preconditioning techniques for the inexact second-order methods applied to solve various sparse approximation problems arising in signal/image reconstruction. The preconditioners exploit two features of such problems:

    (i)  sparsity of the solution, and

    (ii) near-orthogonality of the matrices involved.

The latter originates from the restricted isometry properties frequently assumed to hold in such applications. Spectral analysis of the preconditioners and their practical efficiency when solving linear systems in the Newton Conjugate Gradient method will be presented. If time permits then a few comments on some other problems originating from the "Big Data" buzz will also be given.

Jennifer Pestana - A block preconditioner for a C1 biharmonic problem

Discretisation of two-dimensional Dirichlet biharmonic problems by C1 bicubic Hermite finite elements leads to matrices with condition numbers that grow rapidly as the mesh is refined. Thus, for these problems effective preconditioning is almost always essential.

To develop a novel preconditioner, we exploit a natural blocking that arises from grouping like finite element basis functions. In this talk we will describe this preconditioner, which depends only on the matrix entries, and provide some convergence analysis. We also present numerical results that demonstrate the effectiveness of this approach.

This is joint work with Richard Muddle, Matthias Heil, Francoise Tisseur and Milan Mihajlovic.

Daniel Loghin - Block preconditioners for boundary control of elliptic PDE

The discretization of weak formulations of optimal control of elliptic partial differential equations yields optimality conditions in the form of large sparse linear systems with block structure. For distributed control problems a successful approach is provided by Krylov methods equipped with block preconditioners. However, boundary control problems yield structures which pose specific challenges: rank deficient blocks, intractable Schur complements and generally a lack of a methodical strategy for preconditioner design. In this talk we introduce a novel approach based on a certain boundary preconditioning technique involving blocks of discrete fractional Sobolev norms on the boundary. We illustrate our approach on standard elliptic control problems. We present analysis which shows that the resulting iterative method converges independently of the size of the problem. We include numerical results which indicate that performance is only mildly dependent of the control regularisation parameter.