Rutherford Appleton Laboratory, nr Didcot

Partial differential equations (PDEs) with random coefficients are used in computer simulations of physical processes in science, engineering and industry applications with uncertain data. The goal is to obtain quantitative statements on the effect of input data uncertainties for a comprehensive evaluation of simulation results. However, these equations are formulated in a physical domain coupled with a sample space generated by random parameters and are thus very computing-intensive.

We outline the key computational challenges by discussing a model elliptic PDE of single phase subsurface flow in random media. In this application the coefficients are often rough, highly variable and require a large number of random parameters which puts a limit on all existing discretisation methods. To overcome these limits we employ multilevel Monte Carlo (MLMC), a novel variance reduction technique which uses samples computed on a hierarchy of physical grids. In particular, we combine MLMC with mixed finite element discretisations to calculate travel times of particles in groundwater flows.

For coefficients which can be parameterised by a small number of random variables we employ spectral stochastic Galerkin (SG) methods which give rise to a coupled system of deterministic PDEs. Since the standard SG formulation of the model elliptic PDE requires expensive matrix-vector products we reformulate it as a convection-diffusion problem with random convective velocity. We construct and analyse block-diagonal preconditioners for the nonsymmetric Galerkin matrix for use with Krylov subspace methods such as GMRES.

Uncertainty quantification can begin by specifying the initial state of a system as a probability measure. Part of the state (the 'parameters') might not evolve, and might not be directly observable. Many inverse problems are generalisations of uncertainty quantification such that one modifies the probability measure to be consistent with measurements, a forward model and the initial measure. The inverse problem, interpreted as computing the posterior probability measure of the states, including the parameters and the variables, from a sequence of noise-corrupted observations, is reviewed in the talk. Bayesian statistics provides a natural framework for a solution but leads to very challenging computational problems, particularly when the dimension of the state space is very large, as when arising from the discretisation of a partial differential equation theory.

\\

\\

In this talk we show how the Bayesian framework leads to a new algorithm - the 'Variational Smoothing Filter' - that unifies the leading techniques in use today. In particular the framework provides an interpretation and generalisation of Tikhonov regularisation, a method of forecast verification and a way of quantifying and managing uncertainty. To deal with the problem that a good initial prior may not be Gaussian, as with a general prior intended to describe, for example a geological structure, a Gaussian mixture prior is used. This has many desirable properties, including ease of sampling to make 'numerical rocks' or 'numerical weather' for visualisation purposes and statistical summaries, and in principle can approximate any probability density. Robustness is sought by combining a variational update with this full mixture representation of the conditional posterior density.

The advent of multicore processors represents a disruptive event in the history of computer science as conventional parallel programming paradigms are proving incapable of fully exploiting their potential for concurrent computations. The need for different or new programming models clearly arises from recent studies which identify fine-granularity and dynamic execution as the keys to achieve high efficiency on multicore systems. This talk shows how these models can be effectively applied to the multifrontal method for the QR factorization of sparse matrices providing a very high efficiency achieved through a fine-grained partitioning of data and a dynamic scheduling of computational tasks relying on a dataflow parallel programming model. Moreover, preliminary results will be discussed showing how the multifrontal QR factorization can be accelerated by using low-rank approximation techniques.

Computing the eigenvalue decomposition of a symmetric matrix and the singular value decomposition of a general matrix are two of the central tasks in numerical linear algebra. There has been much recent work in the development of linear algebra algorithms that minimize communication cost. However, the reduction in communication cost sometimes comes at the expense of significantly more arithmetic and potential instability.

\\

\\

In this talk I will describe algorithms for the two decompositions that have optimal communication cost and arithmetic cost within a small factor of those for the best known algorithms. The key idea is to use the best rational approximation of the sign function, which lets the algorithm converge in just two steps. The algorithms are backward stable and easily parallelizable. Preliminary numerical experiments demonstrate their efficiency.

There is a growing interest in the study of periodic phenomena in

large-scale nonlinear dynamical systems. Often the high-dimensional

system has only low-dimensional dynamics, e.g., many reaction-diffusion

systems or Navier-Stokes flows at low Reynolds number. We present an

approach that exploits this property in order to compute branches of

periodic solutions of the large system of ordinary differential

equations (ODEs) obtained after a space discretisation of the PDE. We

call our approach the Newton-Picard method. Our method is based on the

recursive projection method (RPM) of Shroff and Keller but extends this

method in many different ways. Our technique tries to combine the

performance of straightforward time integration with the advantages of

solving a nonlinear boundary value problem using Newton's method and a

direct solver. Time integration works well for very stable limit

cycles. Solving a boundary value problem is expensive, but works also

for unstable limit cycles.

\\

\\

We will present some background material on RPM. Next we will explain

the basic features of the Newton-Picard method for single shooting. The

linearised system is solved by a combination of direct and iterative

techniques. First, we isolate the low-dimensional subspace of unstable

and weakly stable modes (using orthogonal subspace iteration) and

project the linearised system on this subspace and on its

(high-dimensional) orthogonal complement. In the high-dimensional

subspace we use iterative techniques such as Picard iteration or GMRES.

In the low-dimensional (but "hard") subspace, direct methods such as

Gaussian elimination or a least-squares are used. While computing the

projectors, we also obtain good estimates for the dominant,

stability-determining Floquet multipliers. We will present a framework

that allows us to monitor and steer the convergence behaviour of the

method.

\\

\\

RPM and the Newton-Picard technique have been developed for PDEs that

reduce to large systems of ODEs after space discretisation. In fact,

both methods can be applied to any large system of ODEs. We will

indicate how these methods can be applied to the discretisation of the

Navier-Stokes equations for incompressible flow (which reduce to an

index-2 system of differential-algebraic equations after space

discretisation when written in terms of velocity and pressure.)

\\

\\

The Newton-Picard method has already been extended to the computation

of bifurcation points on paths of periodic solutions and to multiple

shooting. Extension to certain collocation and finite difference

techniques is also possible.

The talk will focus on solution methods for augmented linear systems of

the form

\\

\\

$[ A B ][x] = [b] [ B' 0 ][y] [0]$.

\\

\\

Augmented linear systems of this type arise in several areas of

numerical applied mathematics including mixed finite element / finite

difference discretisations of flow equations (Darcy flow and Stokes

flow), electrical network simulation and optimisation. The general

properties of such systems are that they are large, sparse and

symmetric, and efficient solution techniques should make use of the

block structure inherent in the system as well as of these properties.

\\

\\

Iterative linear solution methods will be described that

attempt to take advantage of the structure of the system, and

observations on augmented

systems, in particular the distribution of their eigenvalues, will be

presented which lead to further iterative methods and also to

preconditioners for existing solution methods. For the particular case

of Darcy flow, comments on properties of domain decomposition methods

of additive Schwarz type and similarities to incomplete factorisation

preconditioners will be made.

The Cholesky factorization approach to solving the symmetric definite generalized eigenvalue problem

$Ax = \lambda Bx$, where $A$ is symmetric and $B$ is symmetric positive definite, computes a Cholesky factorization $B = LL^T$ and solves the equivalent standard symmetric eigenvalue problem $C y = \l y$ where $C = L^{-1} A L^{-T}$. Provided that a stable eigensolver is used, standard error analysis says that the computed eigenvalues are exact for $A+\dA$ and $B+\dB$ with $\max( \normt{\dA}/\normt{A}, \normt{\dB}/\normt{B} )$

bounded by a multiple of $\kappa_2(B)u$, where $u$ is the unit roundoff. We take the Jacobi method as the eigensolver and explain how backward error bounds potentially much smaller than $\kappa_2(B)u$ can be obtained.

To show the practical utility of our bounds we describe a vibration problem from structural engineering in which $B$ is ill conditioned yet the error bounds are small. We show how, in cases of instability, iterative refinement based on Newton's method can be used to produce eigenpairs with small backward errors.

Our analysis and experiments also give insight into the popular Cholesky--QR method used in LAPACK, in which the QR method is used as the eigensolver.

We combine linear algebra techniques with finite element techniques to obtain a reliable stopping criterion for the Conjugate Gradient algorithm. The finite element method approximates the weak form of an elliptic partial differential equation defined within a Hilbert space by a linear system of equations A x = b, where A is a real N by N symmetric and positive definite matrix. The conjugate gradient method is a very effective iterative algorithm for solving such systems. Nevertheless, our experiments provide very good evidence that the usual stopping criterion based on the Euclidean norm of the residual b - Ax can be totally unsatisfactory and frequently misleading. Owing to the close relationship between the conjugate gradient behaviour and the variational properties of finite element methods, we shall first summarize the principal properties of the latter. Then, we will use the recent results of [1,2,3,4]. In particular, using the conjugate gradient, we will compute the information which is necessary to evaluate the energy norm of the difference between the solution of the continuous problem, and the approximate solution obtained when we stop the iterations by our criterion.

Finally, we will present the numerical experiments we performed on a selected ill-conditioned problem.

References

• [1] M. Arioli, E. Noulard, and A. Russo, Vector Stopping Criteria for Iterative Methods: Applications to PDE's, IAN Tech. Rep. N.967, 1995.
• [2] G.H. Golub and G. Meurant, Matrices, moments and quadrature II; how to compute the norm of the error in iterative methods, BIT., 37 (1997), pp.687-705.
• [3] G.H. Golub and Z. Strakos, Estimates in quadratic formulas, Numerical Algorithms, 8, (1994), pp.~241--268.
• [4] G. Meurant, The computation of bounds for the norm of the error in the conjugate gradient algorithm, Numerical Algorithms, 16, (1997), pp.~77--87.