期刊
SIAM REVIEW
卷 59, 期 3, 页码 547-587出版社
SIAM PUBLICATIONS
DOI: 10.1137/15M1040827
关键词
dimension reduction; randomized algorithm; eigenvalue problem; matrix exponentiation; diffusion Monte Carlo; quantum Monte Carlo
资金
- DARPA [D15AP00109]
- AFOSR [FA9550-13-1- 0133]
- NSF [IIS-1546413, DMS-1209136, DMS-1057064]
- Advance Scientific Computing Research program within the DOE Office of Science [DE-SC0014205]
- Argonne, U.S. Department of Energy Office of Science laboratory
- U.S. Department of Energy (DOE) [DE-SC0014205] Funding Source: U.S. Department of Energy (DOE)
- Direct For Computer & Info Scie & Enginr
- Div Of Information & Intelligent Systems [1546413] Funding Source: National Science Foundation
- Direct For Mathematical & Physical Scien
- Division Of Mathematical Sciences [1209136, 1057064] Funding Source: National Science Foundation
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 have dramatically reduced operations and storage cost per iteration (as low as constant under appropriate conditions) and are rather versatile: we will show how they apply to the 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 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 O(n)) may be too big to store or manipulate. In fact, our work is motivated by recent diffusion Monte Carlo based quantum Monte Carlo schemes that have been applied to matrices as large as 10(108) x 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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据