Past Seminars

Thu, 07/03/2002
14:00 		Dr Alison Ramage and Prof Howard Elman (University of Strathclyde and University of Maryland) Computational Mathematics and Applications Add to calendar Comlab
Oscillations in discrete solutions to the convection-diffusion equation
It is well known that discrete solutions to the convection-diffusion equation contain nonphysical oscillations when boundary layers are present but not resolved by the discretisation. For the Galerkin finite element method with linear elements on a uniform 1D grid, a precise statement as to exactly when such oscillations occur can be made, namely, that for a problem with mesh size h, constant advective velocity and different values at the left and right boundaries, oscillations will occur if the mesh Péclet number $ P_e $ is greater than one. In 2D, however, the situation is not so well understood. In this talk, we present an analysis of a 2D model problem on a square domain with grid-aligned flow which enables us to clarify precisely when oscillations occur, and what can be done to prevent them. We prove the somewhat surprising result that there are oscillations in the 2D problem even when $ P_e $ is less than 1. Also, we show that there are distinct effects arising from differences in the top and bottom boundary conditions (equivalent to those seen in 1D), and the non-zero boundaries parallel to the flow direction.
Thu, 28/02/2002
14:00 		Dr Yves Tourigny (University of Bristol) Computational Mathematics and Applications Add to calendar Comlab
The dynamics of Pade aproximation
Thu, 21/02/2002
14:00 		Dr Alexander Meeraus (GAMS Development Corporation, Washington DC) Computational Mathematics and Applications Add to calendar Rutherford Appleton Laboratory, nr Didcot
Algebraic modeling systems and mathematical programming
Algebra based modeling systems are becoming essential elements in the application of large and complex mathematical programs. These systems enable the abstraction, expression and translation of practical problems into reliable and effective operational systems. They provide the bridged between algorithms and real world problems by automating the problem analysis and translation into specific data structures and provide computational services required by different solvers. The modeling system GAMS will be used to illustrate the design goals and main features of such systems. Applications in use and under development will be used to provide the context for discussing the changes in user focus and future requirements. This presents new sets of opportunities and challenges to the supplier and implementer of mathematical programming solvers and modeling systems.
Thu, 14/02/2002
14:00 		Dr Roland Becker (University of Heidelberg) Computational Mathematics and Applications Add to calendar Comlab
Adaptive finite elements for optimal control
A systematic approach to error control and mesh adaptation for optimal control of systems governed by PDEs is presented. Starting from a coarse mesh, the finite element spaces are successively enriched in order to construct suitable discrete models. This process is guided by an a posteriori error estimator which employs sensitivity factors from the adjoint equation. We consider different examples with the stationary Navier-Stokes equations as state equation.
Thu, 07/02/2002
14:00 		Dr Alexey Shadrin (DAMPT, University of Cambridge) Computational Mathematics and Applications Add to calendar Comlab
On the condition number of bases in Banach spaces
Thu, 31/01/2002
14:00 		Prof Ivan Graham (University of Bath) Computational Mathematics and Applications Add to calendar Rutherford Appleton Laboratory, nr Didcot
Iterative methods for PDE eigenvalue problems
When steady solutions of complex physical problems are computed numerically it is often crucial to compute their stability in order to, for example, check that the computed solution is "physical", or carry out a sensitivity analysis, or help understand complex nonlinear phenomena near a bifurcation point. Usually a stability analysis requires the solution of an eigenvalue problem which may arise in its own right or as an appropriate linearisation. In the case of discretized PDEs the corresponding matrix eigenvalue problem will often be of generalised form:
$ Ax=\lambda Mx $ (1)
with $ A $ and $ M $ large and sparse. In general $ A $ is unsymmetric and $ M $ is positive semi-definite. Only a small number of "dangerous" eigenvalues are usually required, often those (possibly complex) eigenvalues nearest the imaginary axis. In this context it is usually necessary to perform "shift-invert" iterations, which require repeated solution of systems of the form
$ (A - \sigma M)y = Mx $, (2)
for some shift $ \sigma $ (which may be near a spectral point) and for various right-hand sides $ x $. In large applications systems (2) have to be solved iteratively, requiring "inner iterations".

In this talk we will describe recent progress in the construction, analysis and implementation of fast algorithms for finding such eigenvalues, utilising algebraic domain decomposition techniques for the inner iterations.

In the first part we will describe an analysis of inverse iteration techniques for (1) for a model problem in the presence of errors arising from inexact solves of (2). The delicate interplay between the convergence of the (outer) inverse iteration and the choice of tolerance for the inner solves can be used to determine an efficient iterative method provided a good preconditioner for $ A $ is available.

In the second part we describe an application to the computation of bifurcations in Navier-Stokes problems discretised by mixed finite elements applied to the velocity-pressure formulation. We describe the construction of appropriate preconditioners for the corresponding (3 x 3 block) version of (2). These use additive Schwarz methods and can be applied to any unstructured mesh in 2D or 3D and for any selected elements. An important part of the preconditioner is the adaptive coarsening strategy. At the heart of this are recent extensions of the Bath domain decomposition code DOUG, carried out by Eero Vainikko.

An application to the computation of a Hopf bifurcation of planar flow around a cylinder will be given.

This is joint work with Jörg Berns-Müller, Andrew Cliffe, Alastair Spence and Eero Vainikko and is supported by EPSRC Grant GR/M59075.
Thu, 24/01/2002
14:00 		Prof Lloyd N Trefethen (University of Oxford) Computational Mathematics and Applications Add to calendar Comlab
Numerical Schwarz-Christoffel mapping
Thu, 17/01/2002
14:00 		Prof John Barrett (Imperial College London) Computational Mathematics and Applications Add to calendar Comlab
Finite Element approximation of surfactant spreading on a thin film
Thu, 29/11/2001
14:00 		Prof Alastair Spence (University of Bath) Computational Mathematics and Applications Add to calendar Comlab
Inverse iteration and iterative solves
Thu, 22/11/2001
14:00 		Dr Milan Mihajlovic (University of Manchester) Computational Mathematics and Applications Add to calendar Rutherford Appleton Laboratory, nr Didcot
A new preconditioning technique for the solution of the biharmonic problem
In this presentation we examine the convergence characteristics of a Krylov subspace solver preconditioned by a new indefinite constraint-type preconditioner, when applied to discrete systems arising from low-order mixed finite element approximation of the classical biharmonic problem. The preconditioning operator leads to preconditioned systems having an eigenvalue distribution consisting of a tightly clustered set together with a small number of outliers. We compare the convergence characteristics of a new approach with the convergence characteristics of a standard block-diagonal Schur complement preconditioner that has proved to be extremely effective in the context of mixed approximation methods.

In the second part of the presentation we are concerned with the efficient parallel implementation of proposed algorithm on modern shared memory architectures. We consider use of the efficient parallel "black-box” solvers for the Dirichlet Laplacian problems based on sparse Cholesky factorisation and multigrid, and for this purpose we use publicly available codes from the HSL library and MGNet collection. We compare the performance of our algorithm with sparse direct solvers from the HSL library and discuss some implementation related issues.
Thu, 15/11/2001
14:00 		Dr Raphael Hauser (University of Oxford) Computational Mathematics and Applications Add to calendar Comlab
Distribution tails of condition numbers for the polyhedral conic feasibility problem
(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.
Thu, 08/11/2001
14:00 		Dr Mark Embree (University of Oxford) Computational Mathematics and Applications Add to calendar Comlab
Eigenvalues of Locally Perturbed Toeplitz Matrices
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.
Thu, 01/11/2001
14:00 		Dr Michael Ferris (University of Wisconsin) Computational Mathematics and Applications Add to calendar Comlab
Solution of massive support vector machine problems
We investigate the use of interior-point and semismooth methods for solving quadratic programming problems with a small number of linear constraints, where the quadratic term consists of a low-rank update to a positive semi-definite matrix. Several formulations of the support vector machine fit into this category. An interesting feature of these particular problems is the volume of data, which can lead to quadratic programs with between 10 and 100 million variables and, if written explicitly, a dense $ Q $ matrix. Our codes are based on OOQP, an object-oriented interior-point code, with the linear algebra specialized for the support vector machine application. For the targeted massive problems, all of the data is stored out of core and we overlap computation and I/O to reduce overhead. Results are reported for several linear support vector machine formulations demonstrating that the methods are reliable and scalable and comparing the two approaches.
Thu, 25/10/2001
14:00 		Prof Tim Phillips (University of Aberystwyth) Computational Mathematics and Applications Add to calendar Comlab
Spectral element methods for viscoelastic flow problems
Thu, 18/10/2001
14:00 		Dr Marco Marletta (University of Leicester) Computational Mathematics and Applications Add to calendar Comlab
Spectral inclusion and spectral exactness for non-selfadjoint differential equation eigenproblems
Non-selfadjoint singular differential equation eigenproblems arise in a number of contexts, including scattering theory, the study of quantum-mechanical resonances, and hydrodynamic and magnetohydrodynamic stability theory.

It is well known that the spectra of non-selfadjoint operators can be pathologically sensitive to perturbation of the operator. Wilkinson provides matrix examples in his classical text, while Trefethen has studied the phenomenon extensively through pseudospectra, which he argues are often of more physical relevance than the spectrum itself. E.B. Davies has studied the phenomenon particularly in the context of Sturm-Liouville operators and has shown that the eigenfunctions and associated functions of non-selfadjoint singular Sturm-Liouville operators may not even form a complete set in $ L^2 $.

In this work we ask the question: under what conditions can one expect the regularization process used for selfadjoint singular Sturm-Liouville operators to be successful for non-selfadjoint operators? The answer turns out to depend in part on the so-called Sims Classification of the problem. For Sims Case I the process is not guaranteed to work, and indeed Davies has very recently described the way in which spurious eigenvalues may be generated and converge to certain curves in the complex plane.

Using the Titchmarsh-Weyl theory we develop a very simple numerical procedure which can be used a-posteriori to distinguish genuine eigenvalues from spurious ones. Numerical results indicate that it is able to detect not only the spurious eigenvalues due to the regularization process, but also spurious eigenvalues due to the numerics on an already-regular problem. We present applications to quantum mechanical resonance calculations and to the Orr-Sommerfeld equation.

This work, in collaboration with B.M. Brown in Cardiff, has recently been generalized to Hamiltonian systems.
Fri, 12/10/2001
14:00 		Dr Paul Matthews (University of Nottingham) Computational Mathematics and Applications Add to calendar Comlab
Numerical methods for stiff systems of ODEs
Stiff systems of ODEs arise commonly when solving PDEs by spectral methods, so conventional explicit time-stepping methods require very small time steps. The stiffness arises predominantly through the linear terms, and these terms can be handled implicitly or exactly, permitting larger time steps. This work develops and investigates a class of methods known as 'exponential time differencing'. These methods are shown to have a number of advantages over the more well-known linearly implicit methods and integrating factor methods.
Thu, 04/10/2001
14:00 		Dr Todd Munson (Argonne National Laboratories) Computational Mathematics and Applications Add to calendar Comlab
The Kestrel interface to the NEOS server
The Kestrel interface for submitting optimization problems to the NEOS Server augments the established e-mail, socket, and web interfaces by enabling easy usage of remote solvers from a local modeling environment.

Problem generation, including the run-time detection of syntax errors, occurs on the local machine using any available modeling language facilities. Finding a solution to the problem takes place on a remote machine, with the result returned in the native modeling language format for further processing. A byproduct of the Kestrel interface is the ability to solve multiple problems generated by a modeling language in parallel.

This mechanism is used, for example, in the GAMS/AMPL solver available through the NEOS Server, which internally translates a submitted GAMS problem into AMPL. The resulting AMPL problem is then solved through the NEOS Server via the Kestrel interface. An advantage of this design is that the GAMS to AMPL translator does not need to be collocated with the AMPL solver used, removing restrictions on solver choice and reducing administrative costs.

This talk is joint work with Elizabeth Dolan.
Thu, 21/06/2001
14:00 		Prof Gilbert Strang (MIT) Computational Mathematics and Applications Add to calendar Comlab
Tridiagonal matrices and trees
Tridiagonal matrices and three term recurrences and second order equations appear amazingly often, throughout all of mathematics. We won't try to review this subject. Instead we look in two less familiar directions.

Here is a tridiagonal matrix problem that waited surprisingly long for a solution. Forward elimination factors T into LDU, with the pivots in D as usual. Backward elimination, from row n to row 1, factors T into U_D_L_. Parlett asked for a proof that diag(D + D_) = diag(T) + diag(T^-1).^-1. In an excellent paper (Lin Alg Appl 1997) Dhillon and Parlett extended this four-diagonal identity to block tridiagonal matrices, and also applied it to their "Holy Grail" algorithm for the eigenproblem. I would like to make a different connection, to the Kalman filter.

The second topic is a generalization of tridiagonal to "tree-diagonal". Unlike the interval, the tree can branch. In the matrix T, each vertex is connected only to its neighbors (but a branch point has more than two neighbors). The continuous analogue is a second order differential equation on a tree. The "non-jump" conditions at a meeting of N edges are continuity of the potential (N-1 equations) and Kirchhoff's Current Law (1 equation). Several important properties of tridiagonal matrices, including O(N) algorithms, survive on trees.
Thu, 14/06/2001
14:00 		-- Computational Mathematics and Applications Add to calendar Comlab
No seminar
No seminar this week

For any corrections/updates to these listings, please contact seminars [-at-] maths [dot] ox [dot] ac [dot] uk.

Syndicate content