Numerical Analysis and Scientific Computing Seminars 2007/08
Semester One

28 Sep
2007 Matrix SquareRoots with Applications
Daniel Loghin (University of Birmingham)
3.00  Frank Adams Room 1, Alan Turing BuildingAbstract (click to view)Optimal solution methods for certain classes of PDE discretizations require the approximation of boundary operators. An important example is represented by domain decomposition methods where the SteklovPoincare operator needs to be approximated to sufficient accuracy in order to achieve optimality and scalability. Another is that of fourthorder elliptic problems where iterative algorithms are optimal provided two Poisson problems are solved together with a suitable boundary problem. In both cases the boundary operators are norm equivalent to a fractional Sobolev norm of index 1/2 the discretization of which is related to certain matrix square roots. In this talk I will review some standard solution methods for the approximation of boundary operators and discuss the use of Krylov subspace algorithms for the approximation of matrix square roots as preconditioning alternatives.

12 Oct
2007 Dirichlet to Neumann maps for spectral problems
Marco Marletta (Cardiff University)
3.00  Frank Adams Room 1, Alan Turing BuildingAbstract (click to view)This talk will introduce Dirichlet to Neumann maps and their generalizations and explore their analyticity properties and uses in a variety of contexts including:
1. approximation of spectra of PDEs on infinite domains;
2. solution of inverse problems for ODEs, PDEs and block operator matrices. 
26 Oct
2007 The challenge of PDEconstrained optimization
Sue Dollar (Rutherford Appleton Laboratory)
3.00  Frank Adams Room 1, Alan Turing BuildingAbstract (click to view)The term PDEconstrained optimization spans a large range of problems and applications (e.g. aircraft design, image registration, aluminium manufactoring processes...). By considering a simple example I will illustrate some of the challenges involved in the (iterative) solution of such problems and an insight into how some of these issues may be overcome.
This is joint work with Nick Gould (Oxford/RAL), Tyrone Rees (Oxford), Martin Stoll (Oxford) and Andy Wathen (Oxford). 
09 Nov
2007 Polar decompositions in indefinite inner product spaces
Christian Mehl (University of Birmingham)
3.00  Frank Adams Room 1, Alan Turing BuildingAbstract (click to view)In this talk, we discuss polar decompositions in indefinite inner product spaces, i.e., decompositions of a given matrix into a product of two matrices, one being unitary and the other selfadjoint with respect to some indefinite inner product. In contrast to the case of the Euclidean inner product, polar decompositions in indefinite inner products need not always exist and when they exist they need not be unique. This talk gives a short introduction into the theory of polar decompositions and answers the question of existence of polar decompositions by establishing a connection to normal matrices.

13 Nov
2007 Life as a developer of numerical software
Sven Hammarling (NAG)
10.00  Frank Adams Room 1, Alan Turing BuildingAbstract (click to view)I have spent much of my working life concerned with the development of numerical software, starting in 1965 using Algol 60 on an Elliott 803, but perhaps better known more recently for work on the NAG Library and involvement with the Level 2 and 3 BLAS, LAPACK and ScaLAPACK.
In this talk I shall look back at some personal history and important events that have influenced the development of numerical software, as well as trying to bring out principles that I believe are important for numerical software. 
15 Nov
2007 The compensated Horner Scheme and its Performance Evaluation
Nicolas Louvet (Université de Perpignan Via Domitia)
09.00  Frank Adams Room 1, Alan Turing BuildingAbstract (click to view) 
23 Nov
2007 Numerical methods for SDEs with small noise coefficients
Evelyn Buckwar (HeriotWatt University)
3.00  Frank Adams Room 1, Alan Turing BuildingAbstract (click to view)In this talk we will introduce some aspects of stochastic differential equations (SDEs) and their numerics. Then we will deal with SDEs with small noise, which arise in some applications and discuss numerical methods, in particular stochastic linear twostep methods and stochastic RungeKutta methods, for strong approximations of the solutions. Numerical examples will illustrate the results.

07 Dec
2007 Numerical solution of high frequency scattering problems
Stephen Langdon (University of Reading)
3.00  Frank Adams Room 1, Alan Turing BuildingAbstract (click to view)Standard numerical schemes for high frequency scattering problems, with piecewise polynomial approximation spaces, suffer from the debilitating restriction that the number of degrees of freedom required to achieve a prescribed level of accuracy grows at least linearly with respect to the frequency. In this talk we discuss the recent development of boundary integral equation schemes with hybrid approximation spaces, consisting of the products of low order polynomials with highly oscillatory functions, for which it has been demonstrated that the computational cost does not grow significantly as the frequency increases.
Semester Two

01 Feb
2008 Elliptic Reconstruction in A Posteriori Error Analysis for Evolution Equations
Omar Lakkis (University of Sussex)
3.00  Frank Adams Room 1, Alan Turing BuildingAbstract (click to view)I will address the usage of the elliptic reconstruction technique (ERT) in a posteriori error analysis for fully discrete schemes for evolution partial differential equations with particular focus on parabolic equations. A posteriori error estimates are effective tools in error control and adaptivity and a mathematical rigorous derivation justifies and improves their use in practical implementations. The flexibility of the ERT allows a virtually indiscriminate use of various parabolic PDE techniques such as energy methods, duality methods and heatkernel estimates, as opposed to direct approaches which leave less maneuver room. Thanks to the ERT, parabolic stability techniques can be combined with different elliptic a posteriori analysis techniques, such as residual or recovery estimators, to derive a posteriori error bounds. The method unifies and simplifies most previously known analysis, and it provides previously unknown error bounds (e.g., pointwise norm error bounds for the heat equation). [Results with Ch. Makridakis and A. Demlow.] A further feature of the ERT, which I would like to highlight, of the ERT is its simplifying power. It allows to derive estimates where the analysis would be dautingly complicated. As an example, I will illustrate its use in the context of nonconforming methods, with a special eye on discontinuous Galerkin methods [with E. Georgoulis] and "ZZ" recoverytype estimators [with T. Pryer].

15 Feb
2008 Numerical solution of nonlinear matrix equations arising in Markov chains
Bruno Iannazzo (Università dell'Insubria)
2.00  Frank Adams Room 1, Alan Turing BuildingAbstract (click to view)The numerical methods for structured Markov chains are often based on the solution of nonlinear matrix equations, such as the unilateral quadratic matrix equation or the nonsymmetric algebraic Riccati equation. We give a review of the theoretical properties of the equations and we present some reliable algorithms developed so far. In particular we present some recent techniques which allow the algorithms to work well also in the illconditioned cases, when the derivative of the operator defining the equation is singular or nearly singular.

29 Feb
2008 How Many Random Projections Does One Need to Recover a ksparse Vector?
Jared Tanner (University of Edinburgh)
3.00  Frank Adams Room 1, Alan Turing BuildingAbstract (click to view)The essential information contained in most large data sets is small when compared to the size of the data set. +éáThat is, the data can be well approximated using relatively few terms in a suitable transformation. +éáThis paradigm of Compressed Sensing suggests a revolution in how information is collected and processed. In this talk we consider a stronger notion of compressibility, sparsity, which measures the number of nonzero entries. +éáFor data sets which are sparse (possibly following a transformation), the data can often be recovered efficiently, with relatively few randomized measurements by utilizing highly nonlinear optimization based reconstruction techniques. This work was joint with David L. Donoho.

14 Mar
2008 Particlemesh methods for diffeomorphic matching of curves
Colin Cotter (Imperial College London)
3.00  Frank Adams Room 1, Alan Turing BuildingAbstract (click to view)Diffeomorphic matching is a technique for analysing shape information where one seeks a diffeomorphism that takes one shape to another and is "nearest to the identity" with respect to a chosen metric. The technique can be used to classify shapes and perform statistics in a parameterisationfree way. I will describe a particlemesh discretisation for matching curves, and will discuss a few interesting properties of the method when a geometric integrator is used. I will also discuss current work on solver strategies and our applications to bioflow datasets being developed at Imperial College.

11 April
2008 Polynomial Roots, Approximate Greatest Common Divisors and Matrix Rank Estimation
Joab Winkler (University of Sheffield)
3.00  Frank Adams Room 1, Alan Turing BuildingAbstract (click to view)The computation of the roots of a polynomial is a classical problem in mathematics, and numerous algorithms have been developed for their determination. Most of them, however, yield poor results for polynomials that have multiple roots, which is seen computationally by the break up of a multiple root into a cluster of closely spaced simple roots. When, however, structured perturbations that preserve the multiplicities of the roots are imposed on the coefficients, the roots are very wellconditioned because their structured condition numbers are small. This result forms the basis of a polynomial root finding algorithm that also requires approximate greatest common divisor (GCD) computations and the estimation of the rank of a matrix. These topics are discussed in detail, and in particular, it is shown that structured matrix methods applied to a Sylvester resultant matrix can be used to compute an approximate GCD of two inexact polynomials.

25 April
2008 The Envelope Method
Beresford Parlett (UC Berkeley)
3.00  Frank Adams Room 1, Alan Turing BuildingAbstract (click to view)The task is to compute orthogonal eigenvectors (without GramSchmidt) of symmetric tridiagonals for isolated clusters of close eigenvalues. +éáWe review an "old" method, the Submatrix method, and describe an extension which significantly enlarges the scope to include several miniclusters within the given cluster. +éáAn essential feature is to find the envelope of the associated invariant subspace.

2 May
2008 Numerical differential equations without discretization: chebfuns and chebops
Toby Driscoll (University of Delaware)
3.00  Frank Adams Room 1, Alan Turing BuildingAbstract (click to view)In 2004, Battles and Trefethen introduced the "chebfun" system, which a MATLAB package that uses Chebyshev polynomial approximation algorithms to enable working with functions numerically as though they are simple atomic objects. Because the system is based on adaptive function sampling, it rather easily serves as the foundation for adaptive spectral solutions of differential equations. Just as chebfuns hide the details of Chebyshev approximation from the user, a new "chebop" package has been defined to hide the details of spectral DE methods. A chebop object serves as a linear operator on chebfuns, and the systemsolving and eigenvalue functions of MATLAB have been extended to solve adaptively linear boundaryvalue and eigenvalue problems for DEs. In this talk I will introduce the two packages and provide many demonstrations of how they may be used to solve linear and nonlinear boundaryvalue and initialvalue problems. This talk is complementary to the colloquium to be given 11 June 2008 by Prof. L. N. Trefethen.

8 May 2008
Coefficients of Ergodicity: An Introduction
Ilse Ipsen (North Carolina State University)
2.00pm Frank Adams 1 Alan Turing Building 
9 May
2008 Preconditioning for selfadjointness
Andy Wathen (Oxford University)
3.00  Frank Adams Room 1, Alan Turing BuildingAbstract (click to view)Linear Algebra is a major component of many areas of Numerical Analysis from PDEs to Optimization. In the latter area in particular, saddlepoint (or KKT) systems are ubiquitous. As the desire for problems of larger and larger dimension arises (for example from PDE Optimization), iterative linear system solution methods provide the main possible solution approaches. No one wants slow convergence, so preconditioning is almost always needed to ensure adequately rapid convergence. For symmetric matrices, the Conjugate Gradient and MINRES algorithms are methods of choice which are underpinned by descriptive convergence theory that gives clear guidance on desirable preconditioners to enable rapid convergence. For these methods symmetric and positive definite preconditioning is usually employed to preserve symmetry. In this talk I will describe and illustrate with examples useful situations where nonsymmetric preconditioning can be used to give selfadjoint preconditioned matrices in nonstandard inner products. The most longstanding and widely used example is the method of Bramble and Pasciak which arose in the context of the Stokes problem in PDEs  a saddle point system. In these situations symmetric iterative methods can be employed in such inner products with the consequent benefits. This is joint work with Martin Stoll.

17 June
2008 Linearizations of Singular Matrix Polynomials and the Recovery of Minimal Indices
Steve Mackey (Kalamazoo)
10.00  Frank Adams Room 1, Alan Turing BuildingAbstract (click to view)
Further information
For further information please contact the seminar organiser Timo Betcke.