In the following we describe possible projects. Every student needs to con rm his choice of project by e-mail to t.betcke@ucl.ac.uk before the end of Friday 15 March 2013. Not con rming your choice of projects automatically leads to a loss of marks. Once con rmed you are not allowed to change your project any more.
The deadline for submission of the projects is Friday 12 April 2013. See the guidance notes for how to submit your projects.
Project descriptions:
1. Multicanonical Monte Carlo Methods and Rare Growth Factors. One of the big unsolved research problem in Gaussian elimination is the question of backward stability. Even with partial pivoting examples are known, where Gaussian elimination exhibits very large back-
ward errors. The backward stability depends on the so-called growth factor, which states by how much elements of the U matrix grow in comparison to A in the factorisation PA = LU, and matrices are known where the growth-factor depends exponentially on the dimension of the problem. Yet, in practice Gaussian elimination with partial pivoting is a very stable method to compute solutions of systems of linear equations. The question therefore is: "How rare are large growth factors?".
In the paper "Searching for Rare Growth Factors Using Multicanonical Monte Carlo Methods" by Driscoll and Maki, SIAM Review, Vol. 49, pp. 673{692 a numerical procedure based on Monte Carlo simulations is presented to compute the probability of randomly picking a matrix
with a large growth factor.
In this project you are asked to review the history of the investigation into large growth factors and to describe and implement the Multicanonical Monte Carlo approach by Driscoll and Maki in Python to compute the probability distribution function of the growth factor. Lots of variations are possible. You can change the probability distribution function for the matrices, or try for example to nd growth factors in speci c classes of matrices, such as banded or symmetric matrices.
The references given in the paper by Driscoll and Maki provide good pointers to the history of growth factors.
2. Polynomial Interpolation in thousands of points In the paper "Barycentric Lagrange Interpolation" by Berrut and Trefethen, SIAM Review, Vol 46, pp. 501{517 Barycentric Interpolation is reviewed as a method to stably compute interpolation polynomials containing thousands of points. This forms the basis of the successful chebfun Matlab package for representing functions using interpolating polynomials.
In this project you should develop your own ecient implementation of Barycentric interpolation in Python and experiment with it. Investigate the Runge phenomenon, compare interpolation in equidistant nodes with interpolation in Chebychev nodes, and investigate numerically the rate of convergence for functions with various smoothness. Many other investigations are possible, and pointers are given in the paper and the included references.
3. Find your own project. If you have your own idea for a project please come and discuss it with me.