| EPSRC Reference: |
EP/R019215/1 |
| Title: |
Randomized Algorithms for Matrix Computations |
| Principal Investigator: |
Martinsson, Prof. 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: |
|
| EPSRC Industrial Sector Classifications: |
|
| Related Grants: |
|
| Panel History: |
|
|
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
|
|
Impacts |
|
| Description |
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk |
| Summary |
|
| 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 |