17:00
Boundary-value problems for hyperbolic steady-state equations in granular flow
15:45
15:30
14:15
14:15
Coalescence in a random background: do fluctuations matter in the analysis of structured populations?
16:30
16:00
Combinatorial equivalent of non-hyperbolic systems implies topological equivalence
15:45
The restriction property for conformally covariant measures
14:15
Rayleigh processes, real trees, and root growth with re-grafting
FILTRANE, a filter method for the nonlinear feasibility problem
Abstract
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.
A divergence-free element for finite element prediction of radar cross sections
Abstract
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.
Pascal Matrices (and Mesh Generation!)
Abstract
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:
[ 1 0 0 0 ] | [ 1 1 1 1 ] | [ 1 1 1 1] | |||
L = | [ 1 1 0 0 ] | L' = | [ 0 1 2 3 ] | S = | [ 1 2 3 4] |
[ 1 2 1 0 ] | [ 0 0 1 3 ] | [ 1 3 6 10] | |||
[ 1 3 3 1 ] | [ 0 0 0 1 ] | [ 1 4 10 20] |
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 x2 x3 ... ]'.
The third way also gives a proof that S3 = -I but we doubt that result.
The rows of the "hypercube matrix" L2 count corners and edges and faces and ... in n dimensional cubes.
Clustering, reordering and random graphs
Abstract
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 for fluid dynamics problems
Abstract
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.
Inverse eigenvalue problems for quadratic matrix polynomials
Abstract
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.
Modelling bilevel games in electricity
Abstract
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.
Combinatorial structures in nonlinear programming
Abstract
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