Fast randomized iteration: diffusion Monte Carlo through the lens of numerical linear algebra

We review the basic outline of the highly successful diffusion Monte Carlo technique commonly used in contexts ranging from electronic structure calculations to rare event simulation and data assimilation, and show that aspects of the scheme can be extended to address a variety of common tasks in numerical linear algebra. From the point of view of numerical linear algebra, the main novelty of the new algorithms is that they work in either linear or constant cost per iteration (and in total, under appropriate conditions) and are rather versatile: In this article, we will show how they apply to solution of linear systems, eigenvalue problems, and matrix exponentiation, in dimensions far beyond the present limits of numerical linear algebra. In fact, the schemes that we propose are inspired by recent DMC based quantum Monte Carlo schemes that have been applied to matrices as large as 10^108-by-10^108. We will also provide convergence results and discuss the dependence of these results on the dimension of the system. For many problems one can expect the total cost of the schemes to be sub-linear in the dimension of the problem. So while traditional iterative methods in numerical linear algebra were created in part to deal with instances where a matrix (of size O(n^2)) is too big to store, the adaptations of DMC that we propose are intended for instances in which even the solution vector itself (of size O(n)) may be too big to store or manipulate.