Numerical Analysis and Scientific Computing Seminars 2009/10
Semester One
-
02 Oct
2009 A Review of Preconditioning Techniques
for Steady Incompressible Flow
David Silvester (Manchester)
3.00 - Frank Adams Room 1, Alan Turing BuildingAbstract (click to view)Simulation of the motion of an incompressible fluid remains an important and very challenging computational problem. The resources required for accurate modelling of three-dimensional flow test even the most advanced computer hardware.
Mixed finite element approximation of the underlying PDEs leads to symmetric indefinite or unsymmetric indefinite linear systems of equations. In the talk we will review a generic block preconditioning strategy which have the property that the eigenvalues of the preconditioned matrices are contained in intervals that are bounded independently of the mesh size. Although the strategy is well established (original papers by Rusten & Winther, Silvester & Wathen, and Elman & Silvester appeared in the early 1990's) there have been some important and exciting developments in the last couple of years.
Two such developments are discussed in this talk. First, we will present numerical results showing the e ectiveness of an algebraic multigrid implementation of our preconditioning strategy when modelling ground-water flow in porous media that exhibit random spatial variability [1]. Second, we will discuss improvements to the "textbook" methodology, see [2, chap. 8], in the context of solving steady flow problems modelled by the Navier-Stokes equations.
References
[1] Oliver Ernst, Catherine Powell, David Silvester, and Elisabeth Ullmann. Efficient solvers for a linear stochastic Galerkin mixed formulation of diffusion problems with random data. SIAM J. Sci. Comput., 31:1424{1447, 2009.
[2] Howard Elman, David Silvester, and Andy Wathen. Finite Elements and Fast Iterative Solvers: with Applications in Incompressible Fluid Dynamics. Oxford University Press, Oxford, 2005. xiv+400 pp. ISBN: 978-0-19-852868- 5; 0-19-852868-X. -
16 Oct
2009 Evolutionary Equations With Delayed Arguments (Theory, Applications &
Numerics) and their place in the mathematical landscape.
Christopher T. H. Baker (Manchester and Chester)
3.00 - Frank Adams Room 1, Alan Turing BuildingAbstract (click to view)There is a considerable appreciation in the international community of the relevance of evolutionary problems with time lag and the interesting mathematical challenges (in applied analysis, numerical analysis and model identification) that they present. In the UK, interest in these problems could be described as rather sparse but intense in certain hot-spots. One of our aims, in this talk, will be to broaden awareness of the area.
From the theoretical perspective the problems studied are of considerable interest, not least because apparently scalar equations are effectively infinite-dimensional (and smoothness and dynamical properties are complicated). From the modelling perspective they are of interest because many (stochastic and deterministic) problems in modelling relate to situations where there is a realistic time-lag or memory effect, and from the numerical perspective there is a significant impact of these aspects on the numerics and the design of algorithms.
The talk will provide an introduction to the subject and will reflect the speaker's current research interests on issues related to the use of time-lag in computational modelling, and research he has pursued with collaborators. A few of the key important areas that remain to be examined further will be indicated. -
13 Nov
2009
Application of Adaptive Discontinuous Galerkin Methods to Bifurcation Phenomena in Pipe Flows
Paul Houston (Nottingham)
3.00 - Frank Adams Room 1, Alan Turing BuildingAbstract (click to view)In the past, studies of bifurcation phenomena of flow in a cylindrical pipe with a sudden expansion have proven inconclusive. In this work we seek to exploit the O(2)-symmetric properties of the problem, thus making it tractable by reducing the underlying three-dimensional problem to a series of two-dimensional ones. For the numerical solution of the Navier-Stokes equations we employ an interior penalty Discontinuous Galerkin method, together with goal-oriented error estimation techniques to guarantee the accurate identification of bifurcation points.
This research has been carried out in collaboration with Andrew Cliffe and Edward Hall (University of Nottingham), Tom Mullin and James Seddon (University of Manchester), and Eric Phipps and Andy Salinger (Sandia National Laboratories). -
27 Nov
2009
Model Reduction for Unstable Systems
Nancy K. Nichols (Reading)
3.00 - Frank Adams Room 1, Alan Turing BuildingAbstract (click to view) - 04 Dec
2009 Residual and non-residual low-order local projection stabilized
finite element methods
Gabriel R. Barrenechea (Strathclyde)
3.00 - Frank Adams Room 1, Alan Turing BuildingAbstract (click to view)In this talk we will review the recent technique of Local Projection Stabilized (LPS) finite-element methods. This technique will be derived within the enrichment of the finite element space technique, leading to a new family of residual LPS methods. The new methods, being residual, are fully consistent (a property that "classical" LPS do not fulfill). This process is carried out for both the Stokes and linearized Navier-Stokes equation, and the resulting methods analyzed and tested numerically. Finally, for the latter example a new low-order LPS method (non-residual this time) may be obtained by neglecting the cross-terms, thus simplifying the implementation.
-
18 Dec
2009
Finite Difference Approximations of SPDEs
Jochen Voss (Leeds)
3.00 - Frank Adams Room 1, Alan Turing BuildingAbstract (click to view)We study the problems which can occur when naively using finite difference approximations for SPDEs. It transpires that sometimes the discretised equations converge to the "wrong" SPDE when the grid size goes to zero, the error manifests itself as an additional drift term in the limiting equation. We illustrate how one can sometimes guess the form of this additional drift term.
(Joint work with Martin Hairer)
Semester Two
- 12 Feb
2010 Some Numerical Tools for Stochastic Partial Differential Equations.
Mohammed Seaid (Durham University)
3.00 - Frank Adams Room 1, Alan Turing BuildingAbstract (click to view)In this talk we present two numerical techniques for solving stochastic partial differential equations. The stochasticity in these equations can be included as random coefficients in the differential operators or as stochastic excitations in the forcing terms. For linear and semi-linear equations we present results obtained using a coupled spectral Galerkin-characteristic method while a method of lines is used for the case of nonlinear equations. Computational results will be shown for stochastic Burgers and incompressible Navier-Stokes problems, and also for a replicator model in catalyzed RNA-like polymers.
- 19 Feb
2010 Vector extrapolation and applications.
Hassane Sadok (Université du Littoral Cote d'Opale)
3.00 - Frank Adams Room 1, Alan Turing BuildingAbstract (click to view)The convergence of iterates determined by a slowly convergent iterative process often can be accelerated by extrapolation methods. In this talk we will give a survey of vector extrapolation methods such as the reduced rank extrapolation (RRE) of Eddy and Mesina, the minimal polynomial extrapolation (MPE) of Cabay and Jackson, the modified minimal polynomial extrapolation (MMPE) of Brezinski and Pugachev and the topological epsilon-algorithm (TEA) of Brezinski. Using projectors, we derive a different interpretation of these methods and give some theoretical
results. The second part of this talk is devoted to some numerical applications of the vector extrapolation methods to some problems involving linear, nonlinear systems of equations obtained from finite-difference or finite-element discretization of continuum problems.
The truncated singular value decomposition (TSVD) is a popular solution method for small to moderately sized linear ill-posed problems. The truncation index can be thought of as a regularization parameter; its value affects the quality of the computed approximate solution. The choice of a suitable value of the truncation index generally is important, but can be difficult without auxiliary information about the problem being solved.
We will describes how vector extrapolation methods can be combined with TSVD, and illustrates that the determination of the proper value of the truncation index is less critical for the combined extrapolation-TSVD method than for TSVD alone. - 05 Mar
2010 Stationary vector conditioning and eigenvalues for stochastic matrices.
Steve Kirkland (National University of Ireland Maynooth)
3.00 - Frank Adams Room 1, Alan Turing BuildingAbstract (click to view)For an irreducible stochastic matrix A, the left Perron vector v^T, normalised so that its entries sum to 1 is known as the stationary distribution, and carries information about the long-term behaviour of the Markov chain associated with A. How sensitive is the stationary vector to changes in the underlying stochastic matrix? Specifically, if A+E is another irreducible stochastic matrix, with stationary distribution \tilde{v}^T, then we may try to bound v^T - \tilde{v}^T in terms of the size of E. This leads to the notion of a condition number for the stationary distribution - i.e., a function c(A) such that for some suitable pair of norms ||\bullet||_p,||\bullet||_q we have, for any irreducible stochastic A and perturbing matrix E as above, ||v^T - \tilde{v}^T||_p \le c(A)||E||_q. In this talk we will focus on a particular condition number for the stationary distribution, and examine its relationship with the eigenvalues of the underlying stochastic matrix, producing sharp upper and lower bounds on the condition number in terms of the eigenvalues.
- 12 Mar 2010 Quasi-Monte Carlo methods for computing flow in random porous media.
Ivan Graham (Bath)
3.00 - Frank Adams Room 1, Alan Turing BuildingAbstract (click to view)Joint work with Frances Kuo (Sydney), Dirk Nuyens (Leuven), Ian Sloan (Sydney) and Rob Scheichl (Bath).
In this talk we formulate and implement quasi-Monte Carlo (QMC) methods for computing the expectations of functionals of solutions of elliptic PDEs, with coefficients defined as Gaussian random fields. As we see, these methods outperform conventional Monte Carlo methods for such problems. Our main target application is the computation of several quantities of physical interest arising in the modeling of fluid flow in random porous media, such as the effective permeability or the exit time of a plume of pollutants. Such quantities are of great interest in uncertainty quantification in areas such as underground waste disposal, and here QMC is combined with a mixed finite element discretization in space. Our particular emphasis is on relatively high variance and low correlation length, leading to high stochastic dimension, where Karhunen-Loeve expansions converge slowly. In this case Monte Carlo is currently the method of choice but, as we demonstrate, QMC methods are more effective and efficient for a range of parameters and quantities of interest. The talk will discuss both theoretical and computational aspects of this problem and include some applications involving up to 106 stochastic dimensions. - 19 Mar 2010 Leave it to Smith:
Preserving Structure in Matrix Polynomials
Steven Mackey (Western Michigan University)
3.00 - Frank Adams Room 1, Alan Turing BuildingAbstract (click to view)A much-used computational approach to the polynomial eigenvalue problem starts with a linearization of the underlying matrix polynomial P, such as the companion form, and then applies a general-purpose algorithm to the linearization. In applications, however, the polynomial P often has some additional algebraic structure, leading to physically significant spectral symmetries which are important for computational methods to respect. In this situation it can be advantageous to use a linearization with the same structure as P, if one can be found. It turns out that there are structured polynomials for which a linearization with the same structure does not exist. Using the Smith form as the central tool, we describe which matrix polynomials from the classes of alternating, palindromic, and skew-symmetric polynomials allow a linearization with the same structure.
- 26 Mar
2010 Aggregation-based Model Order Reduction for Many-Port Interconnect
Yangfeng Su (Fudan University Shanghai)
3.00 - Frank Adams Room 1, Alan Turing BuildingAbstract (click to view)We propose an efficient Aggregation-based Model Order Reduction method (AMOR) for many-port interconnect circuits. The proposed AMOR method is based on observation that those nodes of interconnect circuits with almost the same voltage can be aggregated together as a “super node” while the input-output characteristics of the network is not significantly changed. Motivated by such an idea, we use an efficient resistance-distance-based spectral clustering method in AMOR method to partition the nodes into clusters with almost the same voltages. The reduced-order model is then obtained by aggregating the nodes within clusters together as “super nodes” in AMOR method. The efficiency of AMOR method is not limited by the numbers of terminals of the networks. Numerical results have demonstrated that the reduced-order models obtained by AMOR can achieve higher simulation efficiency in terms of accuracy and CPU time than the reduced-order models obtained by the state-of-the-art elimination based methods.
- 21 May 2010 Exact Moment Simulation using Random Orthogonal Matrices
Daniel Ledermann (University of Reading)
3.00 - Frank Adams Room 1, Alan Turing BuildingAbstract (click to view)In this talk we present a new method for simulating multivariate samples. The work was motivated by the simulation error inherent in Monte Carlo methods. We first establish the conditions for exact covariance simulation. However, such conditions overlook the higher order moments of a sample. This led to the development of a new simulation technique, which targets multivariate skewness and kurtosis in a semi-parametric framework. Fundamental to this simulation methodology is a new class of rectangular orthogonal matrices. These ``L-matrices'' can be deterministic, parametric or data specific in nature. Infinitely many random samples may be generated by multiplying an L-matrix by arbitrary random orthogonal matrices. The methodology is thus termed ``ROM simulation''. We apply this technique to two problems in finance; estimating the Value-at-Risk (VaR) of an equity portfolio and optimising portfolio weights with conditional VaR.
Further information
For further information please contact the Seminar organiser Younes Chahlaoui.