Spring 2022

Mike O'Neil (oneil@cims.nyu.edu)

Jonathan Weare (weare@cims.nyu.edu)

As the dimension of a matrix grows, standard dense numerical linear algebra algorithms will fail to perform well due to their inherent computational complexity, often quadratic or cubic in the dimension of the matrix. Recently, methods of randomization have been introduced which can partially overcome this computational complexity growth, oftentimes even avoiding a significant loss in precision. This course will serve as an overview of this class of randomized techniques, how they work in practice, the underlying analysis of accuracy guarantees, and modern applications of such techniques to problems in math, physics, chemistry, and statistics. View the syllabus for more detailed information.

Monday 11:00am - 12:50pm, CIWW 1302

(In person)

By appointment

There is no textbook for the course. Course materials will consist of a selection of journal articles and lecture notes. A solid foundation in linear algebra (and numerical linear algebra) is recommended, and we suggest the following sources with regard to those topics:

- L. N. Trefethen and D. Bau, Numerical Linear Algebra, SIAM, 1997

- P. Lax, Linear Algebra and its Applications, Wiley, 2007

There will be a final presentation in the course, consisting of a project or a detailed presentation of a relevant journal paper. The final grade will be determined based on this presentation and class participation.

None.

Date | Topics | Materials |
---|---|---|

Jan 24 | Overview, background NLA | Notes Recording |

Jan 31 | QR: Gram-Schmidt, Householder, asymptotic cost |
Trefethen & Bau: Lecture 6-11 Notes Recording |

Feb 7 |
SVD, Interpolative decomposition Subspace iteration, preconditioned Jacobi iterations |
Trefethen & Bau: Lectures 4-5, 31 Bathe, 2013 Evans & Missirlis, 1982 Notes |

Feb 14 | Probability and Monte Carlo review | Notes |

Feb 21 | No class, Presidents' Day | |

Feb 28 | Monte Carlo review | Notes |

Mar 7 | Randomized range finding |
Halko, Martinsson, Tropp, SIAM Rev., 2011 Notes |

Mar 14 | No class, Spring break | |

Mar 21 | Subsampled Random Fourier Transform | Notes |

Mar 28 | Randomized projection approximation theory | Notes |

Apr 4 | Probabilistic error bounds, power method | Notes |

Apr 11 |
Randomized matrix peeling Monte Carlo + linear algebra |
Martinsson, SIAM J. Sci. Comput., 2016 Notes |

Apr 18 | Ulam and von Neumann scheme | Notes |

Apr 25 | ||

May 2 | ||

May 9 | Project presentations |