Past events

A new filter method will be presented that attempts to find a feasible

point for sets of nonlinear sets of equalities and inequalities. The

method is intended to work for problems where the number of variables

or the number of (in)equalities is large, or both. No assumption is

made about convexity. The technique used is that of maintaining a list

of multidimensional "filter entries", a recent development of ideas

introduced by Fletcher and Leyffer. The method will be described, as

well as large scale numerical experiments with the corresponding

Fortran 90 module, FILTRANE.

In recent times, research into scattering of electromagnetic waves by complex objects

has assumed great importance due to its relevance to radar applications, where the

main objective is to identify targeted objects. In designing stealth weapon systems

such as military aircraft, control of their radar cross section is of paramount

importance. Aircraft in combat situations are threatened by enemy missiles. One

countermeasure which is used to reduce this threat is to minimise the radar cross

section. On the other hand, there is a demand for the enhancement of the radar cross

section of civilian spacecraft. Operators of communication satellites often request

a complicated differential radar cross section in order to assist with the tracking

of the satellite. To control the radar cross section, an essential requirement is a

capability for accurate prediction of electromagnetic scattering from complex objects.

\\

\\

One difficulty which is encountered in the development of suitable numerical solution

schemes is the existence of constraints which are in excess of those needed for a unique

solution. Rather than attempt to include the constraint in the equation set, the novel

approach which is presented here involves the use of the finite element method and the

construction of a specialised element in which the relevant solution variables are

appropriately constrained by the nature of their interpolation functions. For many

years, such an idea was claimed to be impossible. While the idea is not without its

difficulties, its advantages far outweigh its disadvantages. The presenter has

successfully developed such an element for primitive variable solutions to viscous

incompressible flows and wishes to extend the concept to electromagnetic scattering

problems.

\\

\\

Dr Mack has first degrees in mathematics and aeronautical engineering, plus a Masters

and a Doctorate, both in computational fluid dynamics. He has some thirty years

experience in this latter field. He pioneered the development of the innovative

solenoidal approach for the finite element solution of viscous incompressible flows.

At the time, such a radical idea was claimed in the literature to be impossible.

Much of this early research was undertaken during a six month sabbatical with the

Numerical Analysis Group at the Oxford University Computing Laboratory. Dr Mack has

since received funding from British Aerospace and the United States Department of

Defense to continue this research.

In addition to the announced topic of Pascal Matrices (abstract below) we will speak briefly about more recent work by Per-Olof Persson on generating simplicial meshes on regions defined by a function that gives the distance from the boundary. Our first goal was a short MATLAB code and we just submitted "A Simple Mesh Generator in MATLAB" to SIAM.

This is joint work with Alan Edelman at MIT and a little bit with Pascal. They had all the ideas.

Put the famous Pascal triangle into a matrix. It could go into a lower triangular L or its transpose L' or a symmetric matrix S:

These binomial numbers come from a recursion, or from the formula for i choose j, or functionally from taking powers of (1 + x).

The amazing thing is that L times L' equals S. (OK for 4 by 4) It follows that S has determinant 1. The matrices have other unexpected properties too, that give beautiful examples in teaching linear algebra. The proof of L L' = S comes 3 ways, I don't know which you will prefer:

1. By induction using the recursion formula for the matrix entries.
2. By an identity for the coefficients i+j choose j in S.
3. By applying both sides to the column vector [ 1 x x² x³ ... ]'.

The third way also gives a proof that S³ = -I but we doubt that result.

The rows of the "hypercube matrix" L² count corners and edges and faces and ... in n dimensional cubes.

Seminar moved to Week 8, 19 June 2003.

From the point of view of a numerical analyst, I will describe some algorithms for:

• clustering data points based on pairwise similarity,
• reordering a sparse matrix to reduce envelope, two-sum or bandwidth,
• reordering nodes in a range-dependent random graph to reflect the range-dependency,

and point out some connections between seemingly disparate solution techniques. These datamining problems arise across a range of disciplines. I will mention a particularly new and important application from bioinformatics concerning the analysis of gene or protein interaction data.

Immersed interface methods have been developed for a variety of

differential equations on domains containing interfaces or irregular

boundaries. The goal is to use a uniform Cartesian grid (or other fixed

grid on simple domain) and to allow other boundaries or interfaces to

cut through this grid. Special finite difference formulas are developed

at grid points near an interface that incorporate the appropriate jump

conditions across the interface so that uniform second-order accuracy

(or higher) can be obtained. For fluid flow problems with an immersed

deformable elastic membrane, the jump conditions result from a balance

between the singular force imposed by the membrane, inertial forces if

the membrane has mass, and the jump in pressure across the membrane.

A second-order accurate method of this type for Stokes flow was developed

with Zhilin Li and more recently extended to the full incompressible

Navier-Stokes equations in work with Long Lee.

Feedback design for a second order control system leads to an

eigenstructure assignment problem for a quadratic matrix polynomial. It is

desirable that the feedback controller not only assigns specified

eigenvalues to the second order closed loop system, but also that the

system is robust, or insensitive to perturbations. We derive here new

sensitivity measures, or condition numbers, for the eigenvalues of the

quadratic matrix polynomial and define a measure of robustness of the

corresponding system. We then show that the robustness of the quadratic

inverse eigenvalue problem can be achieved by solving a generalized linear

eigenvalue assignment problem subject to structured perturbations.

Numerically reliable methods for solving the structured generalized linear

problem are developed that take advantage of the special properties of the

system in order to minimize the computational work required.

Electricity markets facilitate pricing and delivery of wholesale power.

Generators submit bids to an Independent System Operator (ISO) to indicate

how much power they can produce depending on price. The ISO takes these bids

with demand forecasts and minimizes the total cost of power production

subject to feasibility of distribution in the electrical network.

\\

\\

Each generator can optimise its bid using a bilevel program or

mathematical program with equilibrium (or complementarity) constraints, by

taking the ISOs problem, which contains all generators bid information, at

the lower level. This leads immediately to a game between generators, where

a Nash equilibrium - at which each generator's bid maximises its profit

provided that none of the other generators changes its bid - is sought.

\\

\\

In particular, we examine the idealised model of Berry et al (Utility

Policy 8, 1999), which gives a bilevel game that can be modelled as an

"equilibrium problem with complementarity constraints" or EPCC.

Unfortunately, like bilevel games, EPCCs on networks may not have Nash

equilibria in the (common) case when one or more of links of the network is

saturated (at maximum capacity). Nevertheless we explore some theory and

algorithms for this problem, and discuss the economic implications of

numerical examples where equilibria are found for small electricity

networks.

Traditional optimisation theory and -methods on the basis of the

Lagrangian function do not apply to objective or constraint functions

which are defined by means of a combinatorial selection structure. Such

selection structures can be explicit, for example in the case of "min",

"max" or "if" statements in function evaluations, or implicit as in the

case of inverse optimisation problems where the combinatorial structure is

induced by the possible selections of active constraints. The resulting

optimisation problems are typically neither convex nor smooth and do not

fit into the standard framework of nonlinear optimisation. Users typically

treat these problems either through a mixed-integer reformulation, which

drastically reduces the size of tractable problems, or by employing

nonsmooth optimisation methods, such as bundle methods, which are

typically based on convex models and therefore only allow for weak

convergence results. In this talk we argue that the classical Lagrangian

theory and SQP methodology can be extended to a fairly general class of

nonlinear programs with combinatorial constraints. The paper is available

at http://www.eng.cam.ac.uk/~ss248/publications.

Is it possible to construct a computational model of the real numbers in which the sign

of every computed result is corrected determined? The answer is yes, both in theory and in

practice. The resulting viewpoint contrasts strongly with the traditional floating

point model. I will review the theoretical background and software design issues,

discuss previous attempts at implementation and finally demonstrate my own python and

C++ codes.

The pseudospectral method for solving boundary value problems on the interval

consists in replacing the solution by an interpolating polynomial in Lagrangian

form between well-chosen points and collocating at those same points.

\\

\\

Due to its globality, the method cannot handle steep gradients well (Markov's inequality).

We will present and discuss two means of improving upon this: the attachment of poles to

the ansatz polynomial, on one hand, and conformal point shifts on the other hand, both

optimally adapted to the problem to be solved.

Dynamic optimisation is a tool that enables the process industries to

compute optimal control strategies for important chemical processes.

Aspen DynamicsTM is a well-established commercial engineering software

package containing a dynamic optimisation tool. Its intuitive graphical

user interface and library of robust dynamic models enables engineers to

quickly and easily define a dynamic optimisation problem including

objectives, control vector parameterisations and constraints. However,

this is only one part of the story. The combination of dynamics and

non-linear optimisation can create a problem that can be very difficult

to solve due to a number of reasons, including non-linearities, poor

initial guesses, discontinuities and accuracy and speed of dynamic

integration. In this talk I will begin with an introduction to process

modelling and outline the algorithms and techniques used in dynamic

optimisation. I will move on to discuss the numerical issues that can

give us so much trouble in practice and outline some solutions we have

created to overcome some of them.

Many questions of interest to both mathematicians and physicists relate

to the behavior of eigenvalues and eigenmodes of the Laplace operator

on a polygon. Algorithmic improvements have revived the old "method

of fundamental solutions" associated with Fox, Henrici and Moler; is it

going to end up competitive with the state-of-the-art method of Descloux,

Tolley and Driscoll? This talk will outline the numerical issues but

give equal attention to applications including "can you hear the shape

of a drum?", localization of eigenmodes, eigenvalue avoidance, and the

design of drums that play chords.

\\

This is very much work in progress -- with graduate student Timo Betcke.

Image processing is an area with many important applications, as well as challenging problems for mathematicians. In particular, Fourier/wavelets analysis and stochastic/statistical methods have had major impact in this area. Recently, there has been increased interest in a new and complementary approach, using partial differential equations (PDEs) and differential-geometric models. It offers a more systematic treatment of geometric features of mages, such as shapes, contours and curvatures, etc., as well as allowing the wealth of techniques developed for PDEs and Computational Fluid Dynamics (CFD) to be brought to bear on image processing tasks.

I'll use two examples from my recent work to illustrate this synergy:

1. A unified image restoration model using Total Variation (TV) which can be used to model denoising, deblurring, as well as image inpainting (e.g. restoring old scratched photos). The TV idea can be traced to shock capturing methods in CFD and was first used in image processing by Rudin, Osher and Fatemi.

2. An "active contour" model which uses a variational level set method for object detection in scalar and vector-valued images. It can detect objects not necessarily defined by sharp edges, as well as objects undetectable in each channel of a vector-valued image or in the combined intensity. The contour can go through topological changes, and the model is robust to noise. The level set method was originally developed by Osher and Sethian for tracking interfaces in CFD.

(The above are joint works with Jackie Shen at the Univ. of Minnesota and Luminita Vese in the Math Dept at UCLA.)

2.00 pm Professor Iain Duff (RAL) Opening remarks

2.15 pm Professor M J D Powell (University of Cambridge)

Some developments of work with Alan on cubic splines

3.00 pm Professor Kevin Burrage (University of Queensland)

Stochastic models and simulations for chemically reacting systems

3.30 pm Tea/Coffee

4.00 pm Professor John Reid (RAL)

Sparse matrix research at Harwell and the Rutherford Appleton Laboratory

4.30 pm Dr Ian Jones (AEA PLC)

Computational fluid dynamics and the role of stiff solvers

5.00 pm Dr Lawrence Daniels (Hyprotech UK Ltd)

Current work with Alan on ODE solvers for HSL

Long-step primal-dual path-following algorithms constitute the

framework of practical interior point methods for

solving linear programming problems. We consider

such an algorithm and a second order variant of it.

We address the problem of the convergence of

the sequences of iterates generated by the two algorithms

to the analytic centre of the optimal primal-dual set.

Several real Lie and Jordan algebras, along with their associated

automorphism groups, can be elegantly expressed in the quaternion tensor

algebra. The resulting insight into structured matrices leads to a class

of simple Jacobi algorithms for the corresponding $n \times n$ structured

eigenproblems. These algorithms have many desirable properties, including

parallelizability, ease of implementation, and strong stability.

A method for computing periodic orbits for the Navier-Stokes

equations will be presented. The method uses a finite-element Galerkin

discretisation for the spatial part of the problem and a spectral

Galerkin method for the temporal part of the problem. The method will

be illustrated by calculations of the periodic flow behind a circular

cylinder in a channel. The problem has a simple reflectional symmetry

and it will be explained how this can be exploited to reduce the cost

of the computations.