Mathematics: Fully Funded EPSRC PhD Scholarship: Non(computability) in Linear Algebra

This scholarship is funded by the Engineering and Physical Sciences Research Council (EPSRC).

*The deadline for full consideration of applications is 1 August 2021. We will accept applications until the position is filled.

Start date: October 2021 or January 2022

Project Supervisor: Dr Arno Pauly

Project description:

Algorithmic questions pertaining to linear algebra are predominately studied by either taking the underlying field to be discrete (e.g. the rationals) or by forgoing a rigorous model of computation and instead focussing on the development of concrete numerical algorithms. Computable analysis provides a convenient framework to simultaneously consider non-discrete fields (e.g. real or complex numbers) and a rigorous model of computation (ultimately founded on Turing machines). However, only few initial investigations have been undertaken so far, and the field is wide open for research by an ambitious PhD student.

Many interesting computational problems in linear algebra will not be computable in general (this holds e.g. for solving systems of linear equations, finding the rank of a matrix or computing the orthogonal complement of a subspace in infinite dimensions). In these cases, it is very interesting to determine how non-computable the problem is, using the framework of Weihrauch degrees. Such results let us draw conclusions to what extent additional input information or a relaxed notion of algorithm can resolve the non-computability.