Forthcoming events in this series


Thu, 20 Jan 2011

14:00 - 15:00
Gibson Grd floor SR

Optimized domain decomposition methods that scale weakly

Dr Sebastien Loisel
(Heriot-Watt University)
Abstract

In various fields of application, one must solve very large scale boundary value problems using parallel solvers and supercomputers. The domain decomposition approach partitions the large computational domain into smaller computational subdomains. In order to speed up the convergence, we have several ``optimized'' algorithm that use Robin transmission conditions across the artificial interfaces (FETI-2LM). It is known that this approach alone is not sufficient: as the number of subdomains increases, the number of iterations required for convergence also increases and hence the parallel speedup is lost. A known solution for classical Schwarz methods as well as FETI algorithms is to incorporate a ``coarse grid correction'', which is able to transmit low-frequency information more quickly across the whole domain. Such algorithms are known to ``scale weakly'' to large supercomputers. A coarse grid correction is also necessary for FETI-2LM methods. In this talk, we will introduce and analyze coarse grid correction algorithms for FETI-2LM domain decomposition methods.

Tue, 07 Dec 2010

14:00 - 15:00
Gibson Grd floor SR

Mathematics enters the picture

Dr. Massimo Fornasier
(Austrian Academy of Sciences)
Abstract

Can one of the most important Italian Renaissance frescoes reduced in hundreds of thousand fragments by a bombing during the Second World War be re-composed after more than 60 years from its damage? Can we reconstruct the missing parts and can we say something about their original color?

In this talk we would like to exemplify, hopefully effectively by taking advantage of the seduction of art, how mathematics today can be applied in real-life problems which were considered unsolvable only few years ago.

Thu, 02 Dec 2010

14:00 - 15:00
Rutherford Appleton Laboratory, nr Didcot

A high performance dual revised simplex solver

Dr Julian Hall
(University of Edinburgh)
Abstract

Implementations of the revised simplex method for solving large scale sparse linear programming (LP) problems are highly efficient for single-core architectures. This talk will discuss the limitations of the underlying techniques in the context of modern multi-core architectures, in particular with respect to memory access. Novel techniques for implementing the dual revised simplex method will be introduced, and their use in developing a dual revised simplex solver for multi-core architectures will be described.

Thu, 25 Nov 2010

14:00 - 15:00
Rutherford Appleton Laboratory, nr Didcot

Primal-dual active set methods for solving Non-local Allen-Cahn Systems

Dr. Vanessa Styles
(University of Sussex)
Abstract

We propose and analyze a primal-dual active set method for local and non-local vector-valued Allen-Cahn variational inequalities.

We show existence and uniqueness of a solution for the non-local vector-valued Allen-Cahn variational inequality in a formulation involving Lagrange multipliers for local and non-local constraints. Furthermore, convergence of the algorithm is shown by interpreting the approach as a semi-smooth Newton method and numerical simulations are presented.

Thu, 18 Nov 2010

14:00 - 15:00
Gibson Grd floor SR

Optimization with time-periodic PDE constraints: Numerical methods and applications

Mr. Andreas Potschka
(University of Heidelberg)
Abstract

Optimization problems with time-periodic parabolic PDE constraints can arise in important chemical engineering applications, e.g., in periodic adsorption processes. I will present a novel direct numerical method for this problem class. The main numerical challenges are the high nonlinearity and high dimensionality of the discretized problem. The method is based on Direct Multiple Shooting and inexact Sequential Quadratic Programming with globalization of convergence based on natural level functions. I will highlight the use of a generalized Richardson iteration with a novel two-grid Newton-Picard preconditioner for the solution of the quadratic subproblems. At the end of the talk I will explain the principle of Simulated Moving Bed processes and conclude with numerical results for optimization of such a process.

Thu, 11 Nov 2010

14:00 - 15:00
Gibson Grd floor SR

Applications of linear barycentric rational interpolation at equidistant points

Prof. Jean-Paul Berrut
(Université de Fribourg)
Abstract

Efficient linear and infinitely smooth approximation of functions from equidistant samples is a fascinating problem, at least since Runge showed in 1901 that it is not delivered by the interpolating polynomial.

In 1988, I suggested to substitute linear rational for polynomial interpolation by replacing the denominator 1 with a polynomial depending on the nodes, though not on the interpolated function. Unfortunately the so-obtained interpolant converges merely as the square of the mesh size. In 2007, Floater and Hormann have given for every integer a denominator that yields convergence of that prescribed order.

In the present talk I shall present the corresponding interpolant as well as some of its applications to differentiation, integration and the solution of boundary value problems. This is joint work with Georges Klein and Michael Floater.

Thu, 04 Nov 2010

14:00 - 15:00
Gibson Grd floor SR

The Convergence Behaviour of BiCG

Prof. Eric de Sturler
(Virginia Tech)
Abstract

The Bi-Conjugate Gradient method (BiCG) is a well-known iterative solver (Krylov method) for linear systems of equations, proposed about 35 years ago, and the basis for some of the most successful iterative methods today, like BiCGSTAB. Nevertheless, the convergence behavior is poorly understood. The method satisfies a Petrov-Galerkin property, and hence its residual is constrained to a space of decreasing dimension (decreasing one per iteration). However, that does not explain why, for many problems, the method converges in, say, a hundred or a few hundred iterations for problems involving a hundred thousand or a million unknowns. For many problems, BiCG converges not much slower than an optimal method, like GMRES, even though the method does not satisfy any optimality properties. In fact, Anne Greenbaum showed that every three-term recurrence, for the first (n/2)+1 iterations (for a system of dimension n), is BiCG for some initial 'left' starting vector. So, why does the method work so well in most cases? We will introduce Krylov methods, discuss the convergence of optimal methods, describe the BiCG method, and provide an analysis of its convergence behavior.

Thu, 28 Oct 2010

14:00 - 15:00
Gibson Grd floor SR

Algebraic multigrid with guaranteed convergence rate

Prof. Yvan Notay
(Universite Libre de Bruxelles)
Abstract

Algebraic multigrid methods are nowadays popular to solve linear systems arising from the discretization of elliptic PDEs. They try to combine the efficiency of well tuned specific schemes like classical (geometric-based) multigrid methods, with the ease of use of general purpose preconditioning techniques. This requires to define automatic coarsening procedures, which set up an hierarchy of coarse representations of the problem at hand using only information from the system matrix.

In this talk, we focus on aggregation-based algebraic multigrid methods. With these, the coarse unknowns are simply formed by grouping variables in disjoint subset called aggregates.

In the first part of the talk, we consider symmetric M-matrices with nonnegative row-sum. We show how aggregates can then be formed in such a way that the resulting method satisfies a prescribed bound on its convergence rate. That is, instead of the classical paradigm that applies an algorithm and then performs its analysis, the analysis is integrated in the set up phase so as to enforce minimal quality requirements. As a result, we obtain one of the first algebraic multigrid method with full convergence proof. The efficiency of the method is further illustrated by numerical results performed on finite difference or linear finite element discretizations of second order elliptic PDEs; the set of problems includes problems with jumps, anisotropy, reentering corners and/or unstructured meshes, sometimes with local refinement.

In the second part of the talk, we discuss nonsymmetric problems. We show how the previous approach can be extended to M-matrices with row- and column-sum both nonnegative, which includes some stable discretizations of convection-diffusion equations with divergence free convective flow. Some (preliminary) numerical results are also presented.

This is joint work with Artem Napov.

Thu, 21 Oct 2010

14:00 - 15:00
Gibson Grd floor SR

Diffuse interface models for two-phase flow

Prof. Axel Voigt
(Dresden University of Technology)
Abstract

Starting from a Navier-Stokes-Cahn-Hilliard equation for a two-phase flow problem we discuss efficient numerical approaches based on adaptive finite element methods. Various extensions of the model are discussed: a) we consider the model on implicitly described geometries, which is used to simulate the sliding of droplets over nano-patterned surfaces, b) we consider the effect of soluble surfactants and show its influence on tip splitting of droplets under shear flow, and c) we consider bijels as a new class of soft matter materials, in which colloidal particles are jammed on the fluid-fluid interface and effect the motion of the interface due to an elastic force.

The work is based on joint work with Sebastian Aland (TU Dresden), John Lowengrub (UC Irvine) and Knut Erik Teigen (U Trondheim).

Thu, 14 Oct 2010

14:00 - 15:00
Gibson Grd floor SR

A Nonlinear Discretization Theory with Applications to Meshfree Methods

Prof. Klaus Böhmer
(Philipps University Marburg)
Abstract

We extend for the first time the linear discretization theory of Schaback, developed for meshfree methods, to nonlinear operator equations, relying heavily on methods of Böhmer, Vol I. There is no restriction to elliptic problems or to symmetric numerical methods like Galerkin techniques.

Trial spaces can be arbitrary, but have to approximate the solution well, and testing can be weak or strong. We present Galerkin techniques as an example. On the downside, stability is not easy to prove for special applications, and numerical methods have to be formulated as optimization problems. Results of this discretization theory cover error bounds and convergence rates. These results remain valid for the general case of fully nonlinear elliptic differential equations of second order. Some numerical examples are added for illustration.

Thu, 07 Oct 2010

14:00 - 15:00
Gibson Grd floor SR

A fast and simple algorithm for the computation of Legendre coefficients

Prof. Arieh Iserles
(University of Cambridge)
Abstract

We present an O(N logN) algorithm for the calculation of the first N coefficients in an expansion of an analytic function in Legendre polynomials. In essence, the algorithm consists of an integration of a suitably weighted function along an ellipse, a task which can be accomplished with Fast Fourier Transform, followed by some post-processing.

Thu, 17 Jun 2010

14:00 - 15:00
3WS SR

Towards Effective Computation with Kernels on Manifolds

Prof Joseph Ward
(Texas A&M University)
Abstract
This talk will focus on highly localized basis functions which exist for certain kernels and spaces associated with these kernels. Such kernels include certain radial basis functions (RBFs), their restrictions to spheres (SBFs), and their restrictions to more general manifolds embeddable in Rd. The first part of the talk will be of an introductory nature. It will discuss radial basis functions and their restriction to manifolds which give rise to various kernels on these manifolds. The talk will then focus on the development (for certain kernels) of highly localized Lagrange functions which serve as effective bases: i.e., bases which are stable and local. Scaled versions of these bases will then be used to establish the stability of the L2 minimization operator in Lp, 1 ≤ p ≤ ∞, thus obtaining a multivariate analogue of a result of de Boor. Since these bases are scalable with the data, they have potential uses beyond approximation including meshless methods and, more generally, computations of a multiresolution nature. The talk is primarily based on joint work with T. Hangelbroek, F. J. Narcowich and X. Sun.
Thu, 27 May 2010

14:00 - 15:00
3WS SR

High-order surface integral algorithms for 3D computational electromagnetics

Prof Mahadevan Ganesh
(Colorado School of Mines)
Abstract

We discuss a class of high-order spectral-Galerkin surface integral algorithms with specific focus on simulating the scattering of electromagnetic waves by a collection of three dimensional deterministic and stochastic particles.

Thu, 20 May 2010

14:00 - 15:00
Rutherford Appleton Laboratory, nr Didcot

Numerical Methods for Monge-Kantorovich Transportation Problems

Dr Jan Van lent
(UWE Bristol)
Abstract

In the eighteenth century Gaspard Monge considered the problem of finding the best way of moving a pile of material from one site to another. This optimal transport problem has many applications such as mesh generation, moving mesh methods, image registration, image morphing, optical design, cartograms, probability theory, etc. The solution to an optimal transport problem can be found by solving the Monge-Amp\`{e}re equation, a highly nonlinear second order elliptic partial differential equation. Leonid Kantorovich, however, showed that it is possible to analyse optimal transport problems in a framework that naturally leads to a linear programming formulation. In recent years several efficient methods have been proposed for solving the Monge-Amp\`{e}re equation. For the linear programming problem, standard methods do not exploit the special properties of the solution and require a number of operations that is quadratic or even cubic in the number of points in the discretisation. In this talk I will discuss techniques that can be used to obtain more efficient methods.

Joint work with Chris Budd (University of Bath).

Thu, 13 May 2010

14:00 - 15:00
3WS SR

RBF collocation methods for delayed differential equations

Dr Francisco Bernal
(OCCAM, University of Oxford)
Abstract

Meshless (or meshfree) methods are a relatively new numerical approach for the solution of ordinary- and partial differential equations. They offer the geometrical flexibility of finite elements but without requiring connectivity from the discretization support (ie a mesh). Meshless methods based on the collocation of radial basis functions (RBF methods) are particularly easy to code, and have a number of theoretical advantages as well as practical drawbacks. In this talk, an adaptive RBF scheme is presented for a novel application, namely the solution of (a rather broad class of) delayed- and neutral differential equations.

Thu, 06 May 2010

14:00 - 15:00
3WS SR

A Preconditioned Conjugate Gradient Method for Optimal Control Problems with Control and State Constraints

Prof Roland Herzog
(Chemnitz University of Technology)
Abstract

We consider saddle point problems arising as (linearized) optimality conditions in elliptic optimal control problems. The efficient solution of such systems is a core ingredient in second-order optimization algorithms. In the spirit of Bramble and Pasciak, the preconditioned systems are symmetric and positive definite with respect to a suitable scalar product. We extend previous work by Schoeberl and Zulehner and consider problems with control and state constraints. It stands out as a particular feature of this approach that an appropriate symmetric indefinite preconditioner can be constructed from standard preconditioners for those matrices which represent the inner products, such as multigrid cycles.

Numerical examples in 2D and 3D are given which illustrate the performance of the method, and limitations and open questions are addressed.

Thu, 29 Apr 2010

14:00 - 15:00
Rutherford Appleton Laboratory, nr Didcot

A Primal-Dual Regularized Interior-Point Method for Convex Quadratic Programs

Prof Dominique Orban
(Canada)
Abstract

Interior-point methods for linear and convex quadratic programming

require the solution of a sequence of symmetric indefinite linear

systems which are used to derive search directions. Safeguards are

typically required in order to handle free variables or rank-deficient

Jacobians. We propose a consistent framework and accompanying

theoretical justification for regularizing these linear systems. Our

approach is akin to the proximal method of multipliers and can be

interpreted as a simultaneous proximal-point regularization of the

primal and dual problems. The regularization is termed "exact" to

emphasize that, although the problems are regularized, the algorithm

recovers a solution of the original problem. Numerical results will be

presented. If time permits we will illustrate current research on a

matrix-free implementation.

This is joint work with Michael Friedlander, University of British Columbia, Canada

Thu, 22 Apr 2010

14:00 - 15:00
3WS SR

Spectral analysis of the discrete Helmholtz operator preconditioned with a shifted Laplacian

Dr Martin van Gijzen
(Delft University of Technology)
Abstract

Shifted Laplace preconditioners have attracted considerable attention as

a technique to speed up convergence of iterative solution methods for the

Helmholtz equation. In the talk we present a comprehensive spectral

analysis of the discrete Helmholtz operator preconditioned with a shifted

Laplacian. Our analysis is valid under general conditions. The propagating

medium can be heterogeneous, and the analysis also holds for different types

of damping, including a radiation condition for the boundary of the computational

domain. By combining the results of the spectral analysis of the

preconditioned Helmholtz operator with an upper bound on the GMRES-residual

norm we are able to derive an optimal value for the shift, and to

explain the mesh-depency of the convergence of GMRES preconditioned

with a shifted Laplacian. We will illustrate our results with a seismic test

problem.

Joint work with: Yogi Erlangga (University of British Columbia) and Kees Vuik (TU Delft)

Thu, 11 Mar 2010

14:00 - 15:00
3WS SR

Nonlinear Eigenvalue Problems

Prof. Yangfeng Su
(Fudan University Shanghai)
Abstract

Nonlinear eigenvalue problem (NEP) is a class of eigenvalue problems where the matrix depends on the eigenvalue. We will first introduce some NEPs in real applications and some algorithms for general NEPs. Then we introduce our recent advances in NEPs, including second order Arnoldi algorithms for large scale quadratic eigenvalue problem (QEP), analysis and algorithms for symmetric eigenvalue problem with nonlinear rank-one updating, a new linearization for rational eigenvalue problem (REP).

Thu, 04 Mar 2010

14:00 - 15:00
3WS SR

Split Bregman methods for L1-Regularized Problems with Applications to Image Processing

Mr. Thomas Goldstein
(University of California, Los Angeles)
Abstract

This talk will introduce L1-regularized optimization problems that arise in image processing, and numerical methods for their solution. In particular, we will focus on methods of the split-Bregman type, which very efficiently solve large scale problems without regularization or time stepping. Applications include image

denoising, segmentation, non-local filters, and compressed sensing.

Thu, 25 Feb 2010

14:00 - 15:00
3WS SR

Numerical Aspects of Optimization in Finance

Prof. Ekkehard Sachs
(University of Trier)
Abstract

There is a widespread use of mathematical tools in finance and its

importance has grown over the last two decades. In this talk we

concentrate on optimization problems in finance, in particular on

numerical aspects. In this talk, we put emphasis on the mathematical problems and aspects, whereas all the applications are connected to the pricing of derivatives and are the

outcome of a cooperation with an international finance institution.

As one example, we take an in-depth look at the problem of hedging

barrier options. We review approaches from the literature and illustrate

advantages and shortcomings. Then we rephrase the problem as an

optimization problem and point out that it leads to a semi-infinite

programming problem. We give numerical results and put them in relation

to known results from other approaches. As an extension, we consider the

robustness of this approach, since it is known that the optimality is

lost, if the market data change too much. To avoid this effect, one can

formulate a robust version of the hedging problem, again by the use of

semi-infinite programming. The numerical results presented illustrate

the robustness of this approach and its advantages.

As a further aspect, we address the calibration of models being used in

finance through optimization. This may lead to PDE-constrained

optimization problems and their solution through SQP-type or

interior-point methods. An important issue in this context are

preconditioning techniques, like preconditioning of KKT systems, a very

active research area. Another aspect is the preconditioning aspect

through the use of implicit volatilities. We also take a look at the

numerical effects of non-smooth data for certain models in derivative

pricing. Finally, we discuss how to speed up the optimization for

calibration problems by using reduced order models.

Thu, 18 Feb 2010

14:00 - 15:00
3WS SR

Saddle point problems in liquid crystal modelling

Dr. Alison Ramage
(University of Strathclyde)
Abstract

Saddle-point problems occur frequently in liquid crystal modelling. For example, they arise whenever Lagrange multipliers are used for the pointwise-unit-vector constraints in director modelling, or in both general director and order tensor models when an electric field is present that stems from a constant voltage. Furthermore, in a director model with associated constraints and Lagrange multipliers, together with a coupled electric-field interaction, a particular ''double'' saddle-point structure arises. This talk will focus on a simple example of this type and discuss appropriate numerical solution schemes.

This is joint work with Eugene C. Gartland, Jr., Department of Mathematical Sciences, Kent State University.