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

Abstract

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 propose a new class of randomized iterative algorithms based on similar principles 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 Fast Randomized Iteration schemes described in this article is that they work in either linear or constant cost per iteration (and in total, under appropriate conditions) and are rather versatile: 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. While traditional iterative methods in numerical linear algebra were created in part to deal with instances where a matrix (of size $\mathcal{O}(n^2)$) is too big to store, the algorithms that we propose are effective even in instances where the solution vector itself (of size $\mathcal{O}(n)$) may be too big to store or manipulate. In fact, our work is motivated by recent DMC based quantum Monte Carlo schemes that have been applied to matrices as large as $10^{108}\times 10^{108}$. We provide basic convergence results, discuss the dependence of these results on the dimension of the system, and demonstrate dramatic cost savings on a range of test problems.

44 pages, 7 figures

References in corpus (2)

• Inhomogeneous backflow transformations in quantum Monte Carlo calculations
• Compressed Modes for Variational Problems in Mathematics and Physics

Cited by in corpus (15)

• NECI: N-Electron Configuration Interaction with emphasis on state-of-the-art stochastic methods
• Adaptive sampling of large deviations
• Coordinate descent full configuration interaction
• Simulations of Trions and Biexcitons in Layered Hybrid Organic-Inorganic Lead Halide Perovskites
• Optimal Orbital Selection for Full Configuration Interaction (OptOrbFCI): Pursuing the Basis Set Limit under a Budget
• Polaron-Depleton Transition in the Yrast Excitations of a One-Dimensional Bose Gas with a Mobile Impurity
• Stochastic differential equation approach to understanding the population control bias in full configuration interaction quantum Monte Carlo
• Theory and Implementation of a Novel Stochastic Approach to Coupled Cluster
• Approximating matrix eigenvalues by subspace iteration with repeated random sparsification
• Full Configuration Interaction Excited-State Energies in Large Active Spaces from Subspace Iteration with Repeated Random Sparsification
• Beyond Walkers in Stochastic Quantum Chemistry: Reducing Error using Fast Randomized Iteration
• Improved Fast Randomized Iteration Approach to Full Configuration Interaction
• Computing large deviation rate functions of entropy production for diffusion processes by an interacting particle method
• Bound excited states of Fröhlich polarons in one dimension
• A Finite Element Configuration Interaction Method for Wigner Localization