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

DOI10.1137/15M1040827MaRDI QIDQ5348329zbMATH OpenOpenAlexFDO

Authors Lek-Heng Lim, Jonathan Weare

Publication date 15 August 2017

Published in SIAM Review (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1508.06104

zbMATH Keywords

dimension reductionconvergencedata assimilationnumerical examplesrandomized algorithmiterative algorithmsrare event simulation

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Iterative numerical methods for linear systems (65F10) Numerical computation of matrix exponential and similar matrix functions (65F60)

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 $mathcalO(n^2)$) is too big to store, the algorithms that we propose are effective even in instances where the solution vector itself (of size $mathcalO(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}imes10^{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.

Recommendations

• Randomized Monte Carlo algorithms for matrix iterations and solving large systems of linear equations
• A new randomized vector algorithm for iterative solution of large linear systems
• Vector Monte Carlo stochastic matrix-based algorithms for large linear systems
• Stochastic algorithms in linear algebra -- beyond the Markov chains and von Neumann-Ulam scheme
• Sparsified Randomization Algorithms for large systems of linear equations and a new version of the Random Walk on Boundary method

Cites work

• scientific article; zbMATH DE number 1049347 (Why is no real title available?)
• scientific article; zbMATH DE number 1103069 (Why is no real title available?)
• scientific article; zbMATH DE number 1972910 (Why is no real title available?)
• scientific article; zbMATH DE number 2106098 (Why is no real title available?)
• scientific article; zbMATH DE number 3194184 (Why is no real title available?)
• scientific article; zbMATH DE number 3196612 (Why is no real title available?)
• scientific article; zbMATH DE number 3088537 (Why is no real title available?)
• A Note on the Inversion of Matrices by Random Walks
• A Retrospective and Prospective Survey of the Monte Carlo Method
• A Stochastic Approximation Method
• A fast randomized algorithm for orthogonal projection
• A fast randomized algorithm for overdetermined linear least-squares regression
• A fast randomized algorithm for the approximation of matrices
• A new iterative Monte Carlo approach for inverse matrix problem
• A patch that imparts unconditional stability to explicit integrators for Langevin-like equations
• A randomized Kaczmarz algorithm with exponential convergence
• A randomized algorithm for principal component analysis
• A randomized algorithm for the decomposition of matrices
• Advanced Lectures on Machine Learning
• Approximate solutions for large transfer matrix problems
• Compressed modes for variational problems in mathematics and physics
• Compressed plane waves yield a compactly supported multiresolution basis for the Laplace operator
• Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication
• Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix
• Fast Monte Carlo Algorithms for Matrices III: Computing a Compressed Approximate Matrix Decomposition
• Fast monte-carlo algorithms for finding low-rank approximations
• Heterogeneous multiscale methods: a review
• Importance sampling for a Monte Carlo matrix multiplication algorithm, with application to information retrieval
• Improved diffusion Monte Carlo
• MONTE CARLO METHODS FOR SOLVING MULTIVARIABLE PROBLEMS
• Matrix algorithms. Vol. 2: Eigensystems
• Multiscale Methods
• Nuclear norm of higher-order tensors
• On the Control of an Interacting Particle Estimation of Schrödinger Ground States
• Random choice solution of hyperbolic systems
• Random-walk interpretations of classical iteration methods
• Randomized algorithms for the low-rank approximation of matrices
• Sequential Monto Carlo techniques for the solution of linear systems
• Sparse dynamics for partial differential equations

Cited in

(9)

• Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication
• Randomized numerical linear algebra: Foundations and algorithms
• Adaptive sampling of large deviations
• The Full Configuration Interaction Quantum Monte Carlo Method through the Lens of Inexact Power Iteration
• CIMBA: fast Monte Carlo generation using cubic interpolation
• A finite element configuration interaction method for Wigner localization
• Randomized Monte Carlo algorithms for matrix iterations and solving large systems of linear equations
• Error estimates on ergodic properties of discretized Feynman-Kac semigroups
• Approximating matrix eigenvalues by subspace iteration with repeated random sparsification

This page was built for publication: Fast randomized iteration: diffusion Monte Carlo through the Lens of numerical linear algebra

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5348329)