# Past Computational Mathematics and Applications Seminar

17 October 2002
14:00
Prof Nick Higham
Abstract

The study of the finite precision behaviour of numerical algorithms dates back at least as far as Turing and Wilkinson in the 1940s. At the start of the 21st century, this area of research is still very active.

We focus on some topics of current interest, describing recent developments and trends and pointing out future research directions. The talk will be accessible to those who are not specialists in numerical analysis.

Specific topics intended to be addressed include

• Floating point arithmetic: correctly rounded elementary functions, and the fused multiply-add operation.
• The use of extra precision for key parts of a computation: iterative refinement in fixed and mixed precision.
• Gaussian elimination with rook pivoting and new error bounds for Gaussian elimination.
• Automatic error analysis.
• Application and analysis of hyperbolic transformations.
• Computational Mathematics and Applications Seminar
10 October 2002
14:00
Prof Beresford Parlett
Abstract
We describe "avoidance of crossing" and its explanation by von Neumann and Wigner. We show Lax's criterion for degeneracy and then discover matrices whose determinants give the discriminant of the given matrix. This yields a simple proof of the bound given by Ilyushechkin on the number of terms in the expansion of the discriminant as a sum of squares. We discuss the 3 x 3 case in detail.
• Computational Mathematics and Applications Seminar
Abstract
The talk will discuss unsymmetric sparse LU factorization based on the Markowitz pivot selection criterium. The key question for the author is the following: Is it possible to implement a sparse factorization where the overhead is limited to a constant times the actual numerical work? In other words, can the work be bounded by o(sum(k, M(k)), where M(k) is the Markowitz count in pivot k. The answer is probably NO, but how close can we get? We will give several bad examples for traditional methods and suggest alternative methods / data structure both for pivot selection and for the sparse update operations.
• Computational Mathematics and Applications Seminar
6 June 2002
14:00
Prof Gilbert Strang and Per-Olof Persson
Abstract
We discuss two filters that are frequently used to smooth data. One is the (nonlinear) median filter, that chooses the median of the sample values in the sliding window. This deals effectively with "outliers" that are beyond the correct sample range, and will never be chosen as the median. A straightforward implementation of the filter is expensive for large windows, particularly in two dimensions (for images). \\ \\ The second filter is linear, and known as "Savitzky-Golay". It is frequently used in spectroscopy, to locate positions and peaks and widths of spectral lines. This filter is based on a least-squares fit of the samples in the sliding window to a polynomial of relatively low degree. The filter coefficients are unlike the equiripple filter that is optimal in the maximum norm, and the "maxflat" filters that are central in wavelet constructions. Should they be better known....? \\ \\ We will discuss the analysis and the implementation of both filters.
• Computational Mathematics and Applications Seminar
23 May 2002
14:00
Dr David Mayers
Abstract
The asymptotic rate of convergence of the trapezium rule is defined, for smooth functions, by the Euler-Maclaurin expansion. The extension to other methods, such as Gauss rules, is straightforward; this talk begins with some special cases, such as Periodic functions, and functions with various singularities. \\ \\ Convergence rates for ODEs (Initial and Boundary value problems) and for PDEs are available, but not so well known. Extension to singular problems seems to require methods specific to each situation. Some of the results are unexpected - to me, anyway.
• Computational Mathematics and Applications Seminar
16 May 2002
14:00
Dr Victor Pereyra
Abstract
In the past few years we have developed some expertise in solving optimization problems that involve large scale simulations in various areas of Computational Geophysics and Engineering. We will discuss some of those applications here, namely: inversion of seismic data, characterization of piezoelectrical crystals material properties, optimal design of piezoelectrical transducers and opto-electronic devices, and the optimal design of steel structures. \\ \\ A common theme among these different applications is that the goal functional is very expensive to evaluate, often, no derivatives are readily available, and some times the dimensionality can be large. \\ \\ Thus parallelism is a need, and when no derivatives are present, search type methods have to be used for the optimization part. Additional difficulties can be ill-conditioning and non-convexity, that leads to issues of global optimization. Another area that has not been extensively explored in numerical optimization and that is important in real applications is that of multiobjective optimization. \\ \\ As a result of these varied experiences we are currently designing a toolbox to facilitate the rapid deployment of these techniques to other areas of application with a minimum of retooling.
• Computational Mathematics and Applications Seminar
2 May 2002
14:00
Prof Tim Barth
Abstract
A-Posteriori Error estimates for high order Godunov finite volume methods are presented which exploit the two solution representations inherent in the method, viz. as piecewise constants $u_0$ and cell-wise $q$-th order reconstructed functions $R^0_q u_0$. The analysis provided here applies directly to schemes such as MUSCL, TVD, UNO, ENO, WENO or any other scheme that is a faithful extension of Godunov's method to high order accuracy in a sense that will be made precise. Using standard duality arguments, we construct exact error representation formulas for derived functionals that are tailored to the class of high order Godunov finite volume methods with data reconstruction, $R^0_q u_0$. We then consider computable error estimates that exploit the structure of higher order Godunov finite volume methods. The analysis technique used in this work exploits a certain relationship between higher order Godunov methods and the discontinuous Galerkin method. Issues such as the treatment of nonlinearity and the optional post-processing of numerical dual data are also discussed. Numerical results for linear and nonlinear scalar conservation laws are presented to verify the analysis. Complete details can be found in a paper appearing in the proceedings of FVCA3, Porquerolles, France, June 24-28, 2002.
• Computational Mathematics and Applications Seminar
Dr Stefano Salvini
Abstract
SMP (Symmetric Multi-Processors) hardware technologies are very popular with vendors and end-users alike for a number of reasons. However, true shared memory parallelism has experienced somewhat slower to take up amongst the scientific-programming community. NAG has been at the forefront of SMP technology for a number of years, and the NAG SMP Library has shown the potential of SMP systems. \\ \\ At the very high end, SMP hardware technologies are used as building blocks of modern supercomputers, which truly consist of clusters of SMP systems, for which no dedicated model of parallelism yet exists. \\ \\ The aim of this talk is to introduce SMP systems and their potential. Results from our work at NAG will also be introduced to show how SMP parallelism, based on a shared memory paradigm, can be used to very good effect and can produce high performance, scalable software. The talk also aims to discuss some aspects of the apparent slow take up of shared memory parallelism and the potential competition from PC (i.e. Intel)-based cluster technology. The talk then aims to explore the potential of SMP technology within "hybrid parallelism", i.e. mixed distributed and shared memory modes, illustrating the point with some preliminary work carried out by the author and others. Finally, a number of potential future challenges to numerical analysts will be discussed. \\ \\ The talk is aimed at all who are interested in SMP technologies for numerical computing, irrespective of any previous experience in the field. The talk aims to stimulate discussion, by presenting some ideas, backing these with data, not to stifle it in an ocean of detail!
• Computational Mathematics and Applications Seminar