Numerical Analysis and Scientific Computing Seminars 2006/07
Semester One

6 Oct
2006 Finite Element Approximation of a CahnHilliardNavierStokes System
David Kay (University of Sussex)
3.00  MSS M12Abstract (click to view)The CahnHilliard equation is a phenomenological model of phase transitions. Coupling the CahnHilliard and NavierStokes equations yields a model for the dynamics of multiphase fluids that is used to model phenomena such as hydrodynamic effects during spinodal decomposition and the behaviour of polymer fluids. An order $h$ error estimate is presented for a semidiscrete finite element approximation to the system. Convergence of the fully discrete system will also be presented, along with an efficient solution technique. Several numerical results will be shown.

13 Oct
2006 Accurate low and high frequency computations for the Laplace eigenvalue problem
Timo Betcke (University of Manchester)
3.00  MSS M12Abstract (click to view)The Laplace eigenvalue problem has a long and interesting history in the Mathematics and Physics community. Mathematicians were intrigued by Kac's question from 1966 if one can "hear the shape of a drum", which was first solved by Gordon, Webb and Wolpert in 1992. Physicists study the behavior of eigenfunctions associated with high energy eigenvalues in the context of quantum chaos theory. Nevertheless, the accurate numerical computation of eigenvalues and eigenfunctions remains a challenge. In this talk we review boundary based methods that approximate eigenfunctions from a space of functions that satisfy the eigenvalue equation but not necessarily the zero Dirichlet or Neumann boundary conditions. We discuss the numerical implementation of these methods and give approximation theoretic convergence results. We present accurate eigenvalue computations on many interesting domains and give an outlook on open questions in the design of these methods.

20 Oct
2006 A derivativefree tolerant line search method for unconstrained optimization
Marcos Raydan (Universidad Central de Venezuela)
3.00  MSS M12Abstract (click to view)A tolerant derivativefree nonmonotone line search technique is proposed and analyzed. Several consecutive increases in the objective function and also non descent directions are allowed for unconstrained minimization. To exemplify the power of this new line search we describe a direct search algorithm in which the directions are chosen randomly. The convergence properties of this random method relies exclusively on the line search technique. We present numerical experiments, to illustrate the advantages of using a derivativefree nonmonotone globalization strategy, with approximatedgradient type methods and also with the inverse SR1 update that could produce non descent directions. In all cases we use a local variation finite differences approximation to the gradient.

3 Nov
2006 Optimization algorithms on matrix manifolds
PierreAntoine Absil (Université Catholique de Louvain, Belgium)
3.00  MSS M12Abstract (click to view)The world abounds with problems that can be formulated as finding an optimum of a realvalued cost function defined on a smooth nonlinear search space. Oftentimes, the search space is a "matrix manifold", in the sense that its points admit natural representations in the form of matrix arrays. In most cases, the nonlinearity of the manifold is due either to matrix orthogonality constraints in the search space, or to invariance properties in the cost function that need to be factored out in order to obtain a nondegenerate optimization problem. In recent years, the importance of optimization problems on manifolds has stimulated the development of geometric optimization algorithms that exploit the differential structure of the manifold search space. In this talk, we give an overview of geometric optimization algorithms and their applications, with an emphasis on the underlying geometric concepts and on the numerical efficacy of the algorithm implementations.

10 Nov
2006 Postprocessing for Stochastic PDEs
Gabriel Lord (HeriotWatt University)
3.00  MSS M12Abstract (click to view)This talk will introduce an exponential type time integrator of stochastic PDEs. We will use a spectal approximation in space and discuss postprocessing. We will investigate when the postprocessing is advantageous and present numerical results.

17 Nov
2006 Minmax principles for rational Hermitian eigenvalue problems in the band structure calculation of semiconductor quantum dots.
Marta Betcke (Hamburg University of Technology)
3.00  MSS M12Abstract (click to view)Minmax principles play an important role in the design of iterative methods for Hermitian eigenvalue problems. However, it is possible to derive minmax characterizations also for certain Hermitian nonlinear eigenvalue problems. One example are rational eigenproblems arising in the band structure calculation of semiconductor quantum dots. In this talk we discuss conditions under which the physically relevant electronic states (the positive eigenvalues smaller than the confinement potential) can be characterized by a minmax principle. We show that these conditions hold for the popular choice of semiconductor heterojunction InAs/GaAs. For the large sparse rational eigenvalue problem that arises after discretization by e.g. finite element methods we propose efficient solution strategies, which exploit the minmax characterization of the eigenvalues.

1 Dec
2006 Programming Parallel Discrete Element Methods
Ian Smith (School of Engineering, University of Manchester)
3.30 (note later start time)  MSS M12Abstract (click to view)A simple elementby element approach to parallelising finite element computations scales well for engineering problems (static equilibrium, propagation, eigenvalue) up to billions of equations on thousands of processors. The method will be described briefly. In a mesh method like FE, 3D problems rapidly involve many internal nodes at which the solution may not be of interest. It is therefore natural to think of boundary element methods. The talk will consider the application of the same ebe library used in FE to BE problems. It seems to work well. The talk will conclude with solution of a practical industrial problem.

15 Dec
2006 Meddling with minerals a molecule at a time
Michele Warren (School of Earth, Atmospheric and Environmental Sciences, University of Manchester)
3.00  MSS M12Abstract (click to view)Many problems in environmental science involve interactions between the surfaces of minerals and ions in solution. Understanding these processes at a molecular level is crucial if the distribution of pollutants and growth of solid phases are to be predicted and controlled. Experiments and simulation can work together to determine molecular mechanisms and a range of computational approaches exist. Both empirical and quantummechanical methods have been used to model minerals, either as infinite periodic solids or 2Dperiodic surfaces, on computing resources from desktop to parallel supercomputing. The main features of these approaches will be described including the approximations that must be made to reach practical schemes. Examples of applications in mineral science will be given and the needs for complementary calculations at other scales will be outlined.

2 Feb
2007 Quadratic matrix polynomials, limit set of pseudospectra and spectral pollution
Lyonell Boulton (HeriotWatt University)
3.00  MSS O10 (NOTE change from usual room)Abstract (click to view)The estimation of the spectrum of a selfadjoint operator is often performed through subspaces of the domain and corresponding truncations of the infinite operator. Standard numerical techniques, such as the finite element method, aim at solving Galerkin approximate problems posed in weak form. Backed by the RayleighRitz variational principle, when applicable, the Galerkin method represents a powerful tool for the analysis of spectral properties of linear operators. Contrary to a common believe, the Galerkin method is not foolproof. One of its main drawbacks is the existence of spurious eigenvalues converging to points not belonging to the spectrum of the original operator. This phenomenon, called spectral pollution, represents a major difficulty when one aims at estimating discrete eigenvalues lying inside gaps of the essential spectrum. A recent procedure has been identified capable of dealing with spectral pollution. The main difference with the Galerkin method lies in the fact that it gives rise to a weak approximate problem which is quadratic in the spectral parameter, instead of linear. In the first part of this talk we will discuss the basics of this "quadratic" method and how to apply it to concrete infinite dimensional operators. In the second part, we will discuss how to prove approximation of the method by reducing the problem to finding limit set of pseudospectra of sequences of quadratic matrix polynomials.

16 Feb
2007 Polar Decompositions and Generalized Inverses of Matrices
Nicholas J. Higham (University of Manchester)
3.00  MSS M12Abstract (click to view)The polar decomposition is a well known matrix decomposition that generalizes the polar representation of a complex number. I will talk about the definition, properties, applications, and computation of the decomposition. Along the way I will introduce the generalized inverse and some of its properties, and explain why it is a useful theoretical tool. The seminar will be broadly accessible and not require specialist knowledge of matrix analysis or numerical analysis.

2 Mar
2007 Discontinuous Galerkin Finite Element Methods for Systems of FirstOrder Partial Differential Equations
Max Jensen (University of Durham)
3.00  MSS M12Abstract (click to view)We focus on the numerical solution of Friedrichs systems by discontinuous Galerkin methods (DGFEMs). Friedrichs systems are boundary value problems with linear firstorder symmetric positive partial differential operators and allow the unified treatment of a wide range of stationary and timedependent problems, ranging from elliptic and parabolic over hyperbolic to changingtype equations. We consider the convergence of the discontinuous Galerkin method in graph spaces, in which the exact solution of the Friedrichs system is only assumed to be weakly differentiable in characteristic direction. We identify criteria under which the finite element solution converges in the energy norm to the discontinuous exact solution.

9 Mar
2007 An Irreversible Model for Phylogenetic Trees
Peter Lancaster (University of Calgary)
3.00  MSS M12Abstract (click to view)Phylogenetic trees are developed from mtDNA data using a timehomogeneous Markov process. In contrast to earlier work, the full freedom of irreversible processes is admitted, and numerical preprocessing strategies are devised and applied. Relative divergence times and the root of the tree are determined directly by the data.

16 Mar
2007 On optimal short recurrences for generating orthogonal Krylov subspace bases
Joerg Liesen (Technical University of Berlin)
3.00  MSS M12Abstract (click to view)In this talk I will discuss necessary and sufficient conditions on a nonsingular matrix $A$, such that for {\em any} initial vector $r_0$, an orthogonal basis of the Krylov subspaces ${\cal K}_n(A,r_0)$ is generated by a short recurrence. Orthogonality here is meant with respect to some unspecified positive definite inner product. This question is closely related to the question of existence of {\em optimal} Krylov subspace solvers for linear algebraic systems, where optimal means the smallest possible error in the norm induced by the given inner product. The conditions on $A$ were first derived and characterized more than 20 years ago by Faber and Manteuffel (SIAM J. Numer. Anal., 21 (1984), pp.~352362). Their main theorem is often quoted and appears to be widely known. Its details and underlying concepts, however, are quite intricate, with some subtleties not covered in the literature. The talk will based on joined work with Vance Faber, Zden{\v e}k Strako{\v s}, and Petr Tich\'y.

20 April
2007 Towards Implementation of Higher Order Discretization Schemes in Computational Aerodynamics.
Natalia Petrovskaya (University of Birmingham)
2.00  MSS M12 (NOTE earlier time)Abstract (click to view)A study of high order discretization schemes is in the mainstream of research in modern computational aerodynamics. Despite the potential benefits of such schemes are huge, they are not widely used in industrial codes, as there are still a number of questions that should be answered prior to generation of a code for reallife applications. In our talk we discuss several simple examples to demonstrate that the implementation of high order schemes may present new difficulties even in case that a wellknown computational problem is solved. In particular, we address a topic of optimal solution reconstruction in high order schemes on unstructured grids. Another important example is given by a problem of flux approximation in high order schemes that require flux balance at grid interfaces.

4 May
2007 Performance Improvement of Shared Memory Parallel Applications
Len Freeman (School of Computer Science, University of Manchester)
3.00  MSS O10 (NOTE change from usual room)Abstract (click to view)The traditional techniques for developing efficient shared memory parallel applications are based on generic approaches that are applicable to any application. An example of such a generic approach is Guided SelfScheduling for loop scheduling. In this seminar it is argued that more effective techniques for developing parallel applications result if semantic information about the application in question is exploited. Two particular techniques, loop scheduling and page migration, are considered and some preliminary results are presented.

15 MayMatrix Computations and the Secular Equation
2007
Gene H Golub (Stanford University)
2.00pm  MSS O10Abstract (click to view)The "secular equation" is a special way of expressing eigenvalue problems in a variety of applications. We describe the secular equation for several problems, viz eigenvalue problems with a linear constraint on the eigenvector and the solution of eigenvalue problems where the given matrix has been modified by a rank one matrix. Next we show how the secular equation can be approximated by use of the lanczos algorithm. Finally, we discuss numerical methods for solving the approximate secular equation.
Semester Two
Further information
For further information please contact the seminar organiser Nick Higham.