University of Oxford

(Joint work with Felipe Cucker and Dennis Cheung, City University of Hong Kong.)

\\

\\

Condition numbers are important complexity-theoretic tools to capture

a "distillation" of the input aspects of a computational problem that

determine the running time of algorithms for its solution and the

sensitivity of the computed output. The motivation for our work is the

desire to understand the average case behaviour of linear programming

algorithms for a large class of randomly generated input data in the

computational model of a machine that computes with real numbers. In

this model it is not known whether linear programming is polynomial

time solvable, or so-called "strongly polynomial". Closely related to

linear programming is the problem of either proving non-existence of

or finding an explicit example of a point in a polyhedral cone defined

in terms of certain input data. A natural condition number for this

computational problem was developed by Cheung and Cucker, and we analyse

its distributions under a rather general family of input distributions.

We distinguish random sampling of primal and dual constraints

respectively, two cases that necessitate completely different techniques

of analysis. We derive the exact exponents of the decay rates of the

distribution tails and prove various limit theorems of complexity

theoretic importance. An interesting result is that the existence of

the k-th moment of Cheung-Cucker's condition number depends only very

mildly on the distribution of the input data. Our results also form

the basis for a second paper in which we analyse the distributions of

Renegar's condition number for the randomly generated linear programming

problem.

Toeplitz matrices enjoy the dual virtues of ubiquity and beauty. We begin this talk by surveying some of the interesting spectral properties of such matrices, emphasizing the distinctions between infinite-dimensional Toeplitz matrices and the large-dimensional limit of the corresponding finite matrices. These basic results utilize the algebraic Toeplitz structure, but in many applications, one is forced to spoil this structure with some perturbations (e.g., by imposing boundary conditions upon a finite difference discretization of an initial-boundary value problem). How do such

perturbations affect the eigenvalues? This talk will address this question for "localized" perturbations, by which we mean perturbations that are restricted to a single entry, or a block of entries whose size remains fixed as the matrix dimension grows. One finds, for a broad class of matrices, that sufficiently small perturbations fail to alter the spectrum, though the spectrum is exponentially sensitive to other perturbations. For larger real single-entry

perturbations, one observes the perturbed eigenvalues trace out curves in the complex plane. We'll show a number of illustrations of this phenomenon for tridiagonal Toeplitz matrices.

\\

\\

This talk describes collaborative work with Albrecht Boettcher, Marko Lindner, and Viatcheslav Sokolov of TU Chemnitz.

The asymptotic rate of convergence of the trapezium rule is

defined, for smooth functions, by the Euler-Maclaurin expansion.

The extension to other methods, such as Gauss rules, is straightforward;

this talk begins with some special cases, such as Periodic functions, and

functions with various singularities.

\\

\\

Convergence rates for ODEs (Initial and Boundary value problems)

and for PDEs are available, but not so well known. Extension to singular

problems seems to require methods specific to each situation. Some of

the results are unexpected - to me, anyway.

We develop an algorithm for estimating the local Sobolev regularity index

of a given function by monitoring the decay rate of its Legendre expansion

coefficients. On the basis of these local regularities, we design and

implement an hp--adaptive finite element method based on employing

discontinuous piecewise polynomials, for the approximation of nonlinear

systems of hyperbolic conservation laws. The performance of the proposed

adaptive strategy is demonstrated numerically.

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.

The seminar will address issues related to numerical simulation

of non-linear behaviour of solid materials to impact loading.

The kinematic and constitutive aspects of the transition from

continuum to discontinuum will be presented as utilised

within an explicit finite element development framework.

Material softening, mesh sensitivity and regularisation of

solutions will be discussed.