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

DOI10.1137/15M1040827zbMATH Open1371.65005arXiv1508.06104OpenAlexW3098761958MaRDI QIDQ5348329FDOQ5348329

Authors: Lek-Heng Lim, Jonathan Weare 

Publication date: 15 August 2017

Published in: SIAM Review (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

Cited In (9)

• Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication
• Randomized numerical linear algebra: Foundations and algorithms
• The Full Configuration Interaction Quantum Monte Carlo Method through the Lens of Inexact Power Iteration
• Adaptive sampling of large deviations
• 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)