Past Computational Mathematics and Applications Seminar

Geometric integration is the numerical integration of a differential equation, while preserving one or more of its geometric/physical properties exactly, i.e. to within round-off error.

Many of these geometric properties are of crucial importance in physical applications: preservation of energy, momentum, angular momentum, phase-space volume, symmetries, time-reversal symmetry, symplectic structure and dissipation are examples. The field has tantalizing connections to dynamical systems, as well as to Lie groups.

In this talk we first present a survey of geometric numerical integration methods for differential equations, and then exemplify this by discussing symplectic vs energy-preserving integrators for ODEs as well as for PDEs.

We discuss numerical methods for the solution of the palindromic eigenvalue problem Ax=λ A^Tx, where A is a complex matrix. Such eigenvalue problems occur, for example, in the vibration analysis of rail tracks.

The structure of palindromic eigenvalue problems leads to a symmetry in the spectrum: all eigenvalues occur in reciprocal pairs. The need for preservation of this symmetry in finite precision arithmetic requires the use of structure-preserving numerical methods. In this talk, we explain how such methods can be derived.

The aim of this talk is to render the power of (short-step) interior-point methods for linear programming (and by extension, convex programming) intuitively understandable to those who have a basic training in numerical methods for dynamical systems solving. The connection between the two areas is made by interpreting line-search methods in a forward Euler framework, and by analysing the algorithmic complexity in terms of the stiffness of the vector field of search directions. Our analysis cannot replicate the best complexity bounds, but due to its weak assumptions it also applies to inexactly computed search directions and has explanatory power for a wide class of algorithms.

Co-Author: Coralia Cartis, Edinburgh University School of Mathematics.

This talk is concerned with the probabilistic behaviour of a condition

number C(A) for the problem of deciding whether a system of n

homogeneous linear inequalities in m unknowns has a non-zero solution.

In the case where the input system is feasible, the exact probability

distribution of the condition number for random inputs is determined,

and a sharp bound for the general case. In particular, for the

expected value of the logarithm log C(A), an upper bound of order

O(log m) (m the number of variables) is presented which does not

depend on the number of inequalities.

The probability distribution of the condition number C(A) is closely

related to the probability of covering the m-sphere with n spherical

caps of a given radius. As a corollary, we obtain bounds on the

probability of covering the sphere with random caps.

The climate is largely determined by the ocean flow, which in itself is driven by wind and by gradients in temperature and salinity. Nowadays numerical models exist that are able to describe the occurring phenomena not only qualitatively but also quantitatively. At the Institute for Marine and Atmospheric research Utrecht (IMAU) a so-called thermohaline circulation model is developed in which methods of dynamical systems theory are used to study the stability of ocean flows. Here bifurcation diagrams are constructed by varying the strength of the forcing, for instance the amount of fresh water coming in from the north due to melting. For every value of the strength we have to solve a nonlinear system, which is handled by a Newton-type method. This produces many linear systems to be solved. 

In the talk the following will be addressed: the form of the system of equations, a special purpose method which uses Trilinos and MRILU. The latter is a multilevel ILU preconditioner developed at Groningen University. Results of the approach obtained on the Dutch national supercomputer will be shown.

For large--scale saddle point problems, the application of exact iterative schemes and preconditioners may be computationally expensive. In practical situations, only approximations to the inverses of the diagonal block or the related cross-product matrices are considered, giving rise to inexact versions of various solvers. Therefore, the approximation effects must be carefully studied. In this talk we study numerical behavior of several iterative Krylov subspace solvers applied to the solution of large-scale saddle point problems. Two main representatives of the segregated solution approach are analyzed: the Schur complement reduction method, based on an (iterative) elimination of primary variables and the null-space projection method which relies on a basis for the null-space for the constraints. We concentrate on the question what is the best accuracy we can get from inexact schemes solving either Schur complement system or the null-space projected system when implemented in finite precision arithmetic. The fact that the inner solution tolerance strongly influences the accuracy of computed iterates is known and was studied in several contexts.

In particular, for several mathematically equivalent implementations we study the influence of inexact solving the inner systems and estimate their maximum attainable accuracy. When considering the outer iteration process our rounding error analysis leads to results similar to ones which can be obtained assuming exact arithmetic. The situation is different when we look at the residuals in the original saddle point system. We can show that some implementations lead ultimately to residuals on the the roundoff unit level independently of the fact that the inner systems were solved inexactly on a much higher level than their level of limiting accuracy. Indeed, our results confirm that the generic and actually the cheapest implementations deliver the approximate solutions which satisfy either the second or the first block equation to the working accuracy. In addition, the schemes with a corrected direct substitution are also very attractive. We give a theoretical explanation for the behavior which was probably observed or it is already tacitly known. The implementations that we pointed out as optimal are actually those which are widely used and suggested in applications.

Multicore chips are nearly ubiquitous in modern machines, and to fully exploit this continuation of Moore's Law, numerical algorithms need to be able to exploit parallelism. We describe recent approaches to both dense and sparse parallel Cholesky factorization on shared memory multicore systems and present results from our new codes for problems arising from large real-world applications. In particular we describe our experiences using directed acyclic graph based scheduling in the dense case and retrofitting parallelism to a

sparse serial solver.

As research in topology optimisation has reached a level of maturity, two main classes of methods have emerged and their applications to real engineering design in industry are increasing. It has therefore become important to identify the limitations and challenges in order to ensure that topology optimisation is appropriately employed during the design process whilst research may continue to offer a more reliable and fast design tool to engineers.

The seminar will begin by introducing the topology optimisation problem and the two popular finite element based approaches. A range of numerical methods used in the typical implementations will be outlined. This will form the basis for the discussion on the short-comings and challenges as an easy-to-use design tool for engineers, particularly in the context of reliably providing the consistent optimum solutions to given problems with minimum a priori information. Another industrial requirement is a fast solution time to easy-to-set-up problems. The seminar will present the recent efforts in addressing some of these issues and the remaining challenges for the future.

Partial differential equations with a nonlinear pointwise constraint defined through a manifold occur in a variety of applications: The magnetization of a ferromagnet can be described by a unit length vector field and the orientation of the rod-like molecules that constitute a liquid crystal is often modeled by a vector field that attains its values in the real projective plane thus respecting the head-to-tail symmetry of the molecules. Other applications arise in geometric

modeling, quantum mechanics, and general relativity. Simple examples reveal that it is impossible to satisfy pointwise constraints exactly by lowest order finite elements. For two model problems we discuss the practical realization of the constraint, the efficient solution of the resulting nonlinear systems of equations, and weak accumulation of approximations at exact solutions.

We focus on domain decomposition methods for systems of PDEs (versus scalar PDEs). The Smith factorization (a "pure" algebra tool) is used systematically to derive new domain decompositions methods for symmetric and unsymmetric systems of PDEs: the compressible Euler equations, the Stokes and Oseen (linearized Navier-Stokes) problem. We will focus on the Stokes system. In two dimensions the key idea is the transformation of the Stokes problem into a scalar bi-harmonic problem. We show, how a proposed domain decomposition method for the bi-harmonic problem leads to a domain decomposition method for the Stokes equations which inherits the convergence behavior of the scalar problem. Thus, it is sufficient to study the convergence of the scalar algorithm. The same procedure can also be applied to the three-dimensional Stokes problem.

The butterfly-shaped Lorenz attractor is a fractal set made up of infinitely many periodic orbits. Ever since Lorenz (1963) introduced a system of three simple ordinary differential equations, much of the discussion of his system and its strange attractor has adopted a dynamical point of view. In contrast, we allow time to be a complex variable and look upon such solutions of the Lorenz system as analytic functions. Formal analysis gives the form and coefficients of the complex singularities of the Lorenz system. Very precise (> 500 digits) numerical computations show that the periodic orbits of the Lorenz system have singularities which obey that form exactly or very nearly so. Both formal analysis and numerical computation suggest that the mathematical analysis of the Lorenz system is a problem in analytic function theory. (Joint work with S. Sahutoglu).

The advent of multicore processors and other technologies like Graphical Processing Units (GPU) will considerably influence future research in High Performance Computing.

To take advantage of these architectures in dense linear algebra operations, new algorithms are

proposed that use finer granularity and minimize synchronization points.

After presenting some of these algorithms, we address the issue of pivoting and investigate randomization techniques to avoid pivoting in some cases.

In the particular case of GPUs, we show how linear algebra operations can be enhanced using

hybrid CPU-GPU calculations and mixed precision algorithms.

This is not intended to be a systematic History, but a selection of highlights, with some digressions, including:

The early days of the Computing Lab;

How the coming of the Computer changed some of the ways we do Computation;

A problem from the Study Groups;

Influence of the computing environment (hardware and software);

Convergence analysis for the heat equation, then and now.

Dirichlet to Neumann maps and their generalizations are exceptionally useful tools in the study of eigenvalue problems for ODEs and PDEs. They also have real physical significance through their occurrence in electrical impedance tomography, with applications to medical imagine, landmine detection and non-destructive testing. This talk will review some of the basic properties of Dirichlet to Neumann maps, some new abstract results which make it easier to use them for a wide variety of models, and some analytical/numerical results which depend on them, including detection and elimination of spectral pollution.

The Jacobi-Davidson method, proposed by Sleijpen and Van der Vorst more than a decade ago, has been successfully used to numerically solve large matrix eigenvalue problems. In this talk we will give an introduction to and an overview of this method, and also point out some recent developments.

The task is to compute orthogonal eigenvectors (without Gram-Schmidt) 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 mini-clusters within the given cluster. An essential feature is to find the envelope of the associated invariant subspace.

"Eigenvalue avoidance" or "level repulsion" refers to the tendency of eigenvalues of matrices or operators to be distinct rather than degenerate.

The mathematics goes back to von Neumann and Wigner in 1929 and touches many subjects including numerical linear algebra, random matrix theory, chaotic dynamics, and number theory.

This talk will be an informal illustrated discussion of various aspects of this phenomenon.