2023 1 MATH7601 Project Descriptions In the following we describe possible projects Every student needs to conrm his choice of project | Assignment Collections

1 MATH7601: Project Descriptions In the following we describe possible projects. Every student needs to conrm his choice of project by e-mail to [email protected] before the end of Friday 15 March 2013. Not conrming your choice of projects automatically leads to a loss of marks. Once conrmed 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 un- solved 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 specic classes of matrices, such as…