EPSRC logo

Details of Grant 

EPSRC Reference: EP/R019215/1
Title: Randomized Algorithms for Matrix Computations
Principal Investigator: Martinsson, Dr P
Other Investigators:
Researcher Co-Investigators:
Project Partners:
Department: Mathematical Institute
Organisation: University of Oxford
Scheme: Standard Research
Starts: 01 April 2018 Ends: 31 March 2021 Value (£): 336,887
EPSRC Research Topic Classifications:
Numerical Analysis
EPSRC Industrial Sector Classifications:
Information Technologies
Related Grants:
Panel History:
Panel DatePanel NameOutcome
29 Nov 2017 EPSRC Mathematical Sciences Prioritisation Panel November 2017 Announced
Summary on Grant Application Form
Many problems of fundamental importance in science, engineering, and data analytics can be expressed as linear algebraic problems involving arrays of numbers called matrices. The proposed research is aimed at developing more efficient algorithms for executing common computations involving matrices such as solving linear systems, computing so called eigenvalues and eigenvectors, and many more.

The new algorithms to be developed are engineered from the ground up to work well in modern computing environments which look quite different from the hardware that was in use at the time when currently used methods were originally developed. Examples of such "new" environments include multicore CPUs, massively multicore GPUs (graphical processing units), computing on data stored on hard drives (so called "out-of-core" computing), or in the "cloud". In all of these environments, a key concern is to minimize communication, or the movement of data. This is in contrast to the objective of minimizing the number of floating point operations required, which used to be the key computational bottleneck.

Technically, the key novelty is that the new algorithms will rely on randomization to resolve certain communication bottlenecks that have hamstrung existing deterministic methods. The new methods will draw on recent work in mathematics and computer science involving so called randomized projections. In particular, the new algorithms can be viewed as extensions of earlier randomized techniques for matrix computations developed by the PI and co-workers. These existing randomized methods have proven to perform dramatically better than existing methods in many important environments, in particular when applied to modern huge datasets. The proposed research will very substantially extend the class of problems to which randomized methods can be applied.

An essential component of the proposed research is to develop mathematical theory that helps us understand properties of randomized projections. The theory will provide precise performance guarantees and will ensure that the research has a lasting impact. Moreover, many of the mathematical techniques that we develop will be helpful in developing methods based on randomized projections for problems that do not directly involve linear algebra such as clustering and nearest neighbor search.

Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:  
Further Information:  
Organisation Website: http://www.ox.ac.uk