Sketching for Scientific Computing - a practical guide |
| | Abstract | An exciting, recent development in numerical linear algebra is the use of randomisation as a resource, often through a process known as sketching, where a large matrix is replaced by smaller matrix that approximates it well. Much of the literature on sketching is either deeply rooted in theoretical computer science, with little attention on practical performance, or concentrated on narrow areas of applications, obscuring the simplicity of the underlying principles. This thesis aims to bridge the gap between theory and practice, and create a framework for sketching applications that makes it easy to identify and apply sketching in a large range of algorithms.
We describe the fundamental theory behind sketching, focusing on the mathematical concept of subspace embeddings. Four different sketching methods are presented and compared in terms of theoretical guarantees and complexities. The practical performance of the above methods is then tested in various linear algebra problems.
Through our review of literature and the performed experiments, we identify three basic operations. These form the cornerstones of most uses of sketching, allowing for a modular approach to constructing algorithms. We find that simple implementations can yield significant computational advantages, often using sketch dimensions well below the theoretical bounds. Usually, the gains come at the price of approximation errors, the measurement and consideration of which is essential for the success of the methods in practice.
Sketching has the potential to be a valuable tool in many areas of scientific computing. It is at its most useful when coupled with domain-specific knowledge used to provide reasonable assumptions, tighter analysis and suitable error measures. Our hope is that this report can serve as a practical guide to understanding the basic theory and computational aspects of sketching, while making the underlying ideas and methods accessible to a larger audience. | | Type | Master's thesis [Academic thesis] | | Year | 2018 | | Publisher | Technical University of Denmark, Department of Applied Mathematics and Computer Science | | Address | Richard Petersens Plads, Building 324, DK-2800 Kgs. Lyngby, Denmark, compute@compute.dtu.dk | | Series | DTU Compute M.Sc.-2018 | | Note | The work was carried out from January 22nd 2018 to June 22nd 2018 under supervision of Associate Professor Martin Skovgaard Andersen, mskan@dtu.dk and Professor Per Christian Hansen, pcha@dtu.dk, both of DTU Compute. | | Electronic version(s) | [pdf] | | Publication link | http://www.compute.dtu.dk/english | | BibTeX data | [bibtex] | | IMM Group(s) | Scientific Computing |
|