Introductory description

This module provides students with knowledge (and practice) of important numerical optimisation concepts at the intersection between mathematics and scientific computing. Algorithmic structures, data structures, numerical method construction and performance assessment will form key parts of the module, with applications and use cases concentrated on topics in linear algebra, signal processing and optimisation.

Module web page

Module aims

Outline syllabus

This is an indicative module outline only to give an indication of the sort of topics that may be covered. Actual sessions held may differ.

• algorithmic structures (iteration, recursion, memorization) and computational complexity
• data structures (linked lists, stacks and queues, binary indexed trees)
• sorting and search algorithms
• Fast Fourier Transform and its applications
• Topics in numerical linear algebra: solving linear systems, conjugate gradient algorithm, singular value decomposition
• unconstrained continuous optimisation: multivariate minimisation, Nelder-Mead algorithm, automatic differentiation, gradient descent
• constrained continuous optimisation: method of Lagrange multipliers, linear programming
• discrete optimisation: Dijkstra's algorithm, dynamic programming, combinatorial optimisation

Learning outcomes

By the end of the module, students should be able to:

• Demonstrate a deep fundamental understanding of the most important computational algorithms used for advanced data analysis, mathematical modelling and optimisation of complex systems.
• Understand algorithmic structures like iteration, recursion and memorization and be able to apply them.
• Perform mathematical manipulation and implement computational problem-solving techniques.
• Identify the most appropriate approach for computational solution of a mathematical problem and understand problems that can arise such as numerical error, poor conditioning or instability.
• Design and apply both discrete and continuous approaches depending on the requirements of a particular problem.
• Develop efficient code for the computational solution and analysis and optimisation problems, select appropriate data structures and algorithms, present and visualise algorithm outputs and results of analyses in a clear and informative way.
• Distinguish the computational complexity of an algorithm and the practical constraints it imposes on problem solving.

Indicative reading list

Lloyd N. Trefethen and David Bau, Numerical Linear Algebra, 3rd Edition, SIAM, 1997.
William H. Press, Saul A. Teukolsky, William T. Vetterling, and Brian P. Flannery. Numerical recipes: The art of scientific computing, 3rd Edition, Cambridge University Press, New York, NY, USA, 2007.
David Kincaid and Ward Cheney. Numerical analysis : mathematics of scientific computing, 3rd Edition, American Mathematical Society, 2009.
Research articles in the field will complement the textbooks above.

Interdisciplinary

The module sits naturally between mathematics, computer science and elements from related disciplines such as
physics, biology or image processing.

Subject specific skills

See learning outcomes: data structure recognition and usage, discrete mathematical analysis, algorithm construction, performance analysis, advanced linear algebra, optimisation techniques.

Transferable skills

Students will acquire key reasoning and problem solving skills which will empower them to address new problems with confidence. This will be grounded in enhanced software development knowledge (including transferable ‘software carpentry’ skills such as version control and continuous integration testing) and deployed for a wide variety of problems in interdisciplinary contexts.