Improved scaling for quantum Monte Carlo on insulators

Kapil Ahuja, Bryan K. Clark, Eric De Sturler, David M. Ceperley, Jeongnim Kim

Research output: Contribution to journalArticle

Abstract

Quantum Monte Carlo (QMC) methods are often used to calculate properties of many body quantum systems. The main cost of many QMC methods, for example, the variational Monte Carlo (VMC) method, is in constructing a sequence of Slater matrices and computing the ratios of determinants for successive Slater matrices. Recent work has improved the scaling of constructing Slater matrices for insulators so that the cost of constructing Slater matrices in these systems is now linear in the number of particles, whereas computing determinant ratios remains cubic in the number of particles. With the long term aim of simulating much larger systems, we improve the scaling of computing the determinant ratios in the VMC method for simulating insulators by using preconditioned iterative solvers. The main contribution of this paper is the development of a method to efficiently compute for the Slater matrices a sequence of preconditioners that make the iterative solver converge rapidly. This involves cheap preconditioner updates, an effective reordering strategy, and a cheap method to monitor instability of incomplete LU decomposition with threshold and pivoting (ILUTP) preconditioners. Using the resulting preconditioned iterative solvers to compute determinant ratios of consecutive Slater matrices reduces the scaling of QMC algorithms from O(n3) per sweep to roughly O(n2), where n is the number of particles, and a sweep is a sequence of n steps, each attempting to move a distinct particle. We demonstrate experimentally that we can achieve the improved scaling without increasing statistical errors. Our results show that preconditioned iterative solvers can dramatically reduce the cost of VMC for large(r) systems.

Original languageEnglish (US)
Pages (from-to)1837-1859
Number of pages23
JournalSIAM Journal on Scientific Computing
Volume33
Issue number4
DOIs
StatePublished - Sep 19 2011

Fingerprint

Quantum Monte Carlo
Insulator
Scaling
Iterative Solvers
Monte Carlo method
Determinant
Monte Carlo methods
Preconditioner
Sweep
Variational Methods
Computing
Costs
LU decomposition
Iterative Solver
Pivoting
Quantum Algorithms
Reordering
Monte Carlo Algorithm
Quantum Systems
Consecutive

Keywords

  • Krylov subspace methods
  • Preconditioning
  • Quantum Monte Carlo
  • Sequence of linear systems
  • Updating preconditioners
  • Variational Monte Carlo

ASJC Scopus subject areas

  • Applied Mathematics
  • Computational Mathematics

Cite this

Improved scaling for quantum Monte Carlo on insulators. / Ahuja, Kapil; Clark, Bryan K.; De Sturler, Eric; Ceperley, David M.; Kim, Jeongnim.

In: SIAM Journal on Scientific Computing, Vol. 33, No. 4, 19.09.2011, p. 1837-1859.

Research output: Contribution to journalArticle

Ahuja, Kapil ; Clark, Bryan K. ; De Sturler, Eric ; Ceperley, David M. ; Kim, Jeongnim. / Improved scaling for quantum Monte Carlo on insulators. In: SIAM Journal on Scientific Computing. 2011 ; Vol. 33, No. 4. pp. 1837-1859.
@article{1635e37a71574069b665f76f1f73d7c1,
title = "Improved scaling for quantum Monte Carlo on insulators",
abstract = "Quantum Monte Carlo (QMC) methods are often used to calculate properties of many body quantum systems. The main cost of many QMC methods, for example, the variational Monte Carlo (VMC) method, is in constructing a sequence of Slater matrices and computing the ratios of determinants for successive Slater matrices. Recent work has improved the scaling of constructing Slater matrices for insulators so that the cost of constructing Slater matrices in these systems is now linear in the number of particles, whereas computing determinant ratios remains cubic in the number of particles. With the long term aim of simulating much larger systems, we improve the scaling of computing the determinant ratios in the VMC method for simulating insulators by using preconditioned iterative solvers. The main contribution of this paper is the development of a method to efficiently compute for the Slater matrices a sequence of preconditioners that make the iterative solver converge rapidly. This involves cheap preconditioner updates, an effective reordering strategy, and a cheap method to monitor instability of incomplete LU decomposition with threshold and pivoting (ILUTP) preconditioners. Using the resulting preconditioned iterative solvers to compute determinant ratios of consecutive Slater matrices reduces the scaling of QMC algorithms from O(n3) per sweep to roughly O(n2), where n is the number of particles, and a sweep is a sequence of n steps, each attempting to move a distinct particle. We demonstrate experimentally that we can achieve the improved scaling without increasing statistical errors. Our results show that preconditioned iterative solvers can dramatically reduce the cost of VMC for large(r) systems.",
keywords = "Krylov subspace methods, Preconditioning, Quantum Monte Carlo, Sequence of linear systems, Updating preconditioners, Variational Monte Carlo",
author = "Kapil Ahuja and Clark, {Bryan K.} and {De Sturler}, Eric and Ceperley, {David M.} and Jeongnim Kim",
year = "2011",
month = "9",
day = "19",
doi = "10.1137/100805467",
language = "English (US)",
volume = "33",
pages = "1837--1859",
journal = "SIAM Journal of Scientific Computing",
issn = "1064-8275",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "4",

}

TY - JOUR

T1 - Improved scaling for quantum Monte Carlo on insulators

AU - Ahuja, Kapil

AU - Clark, Bryan K.

AU - De Sturler, Eric

AU - Ceperley, David M.

AU - Kim, Jeongnim

PY - 2011/9/19

Y1 - 2011/9/19

N2 - Quantum Monte Carlo (QMC) methods are often used to calculate properties of many body quantum systems. The main cost of many QMC methods, for example, the variational Monte Carlo (VMC) method, is in constructing a sequence of Slater matrices and computing the ratios of determinants for successive Slater matrices. Recent work has improved the scaling of constructing Slater matrices for insulators so that the cost of constructing Slater matrices in these systems is now linear in the number of particles, whereas computing determinant ratios remains cubic in the number of particles. With the long term aim of simulating much larger systems, we improve the scaling of computing the determinant ratios in the VMC method for simulating insulators by using preconditioned iterative solvers. The main contribution of this paper is the development of a method to efficiently compute for the Slater matrices a sequence of preconditioners that make the iterative solver converge rapidly. This involves cheap preconditioner updates, an effective reordering strategy, and a cheap method to monitor instability of incomplete LU decomposition with threshold and pivoting (ILUTP) preconditioners. Using the resulting preconditioned iterative solvers to compute determinant ratios of consecutive Slater matrices reduces the scaling of QMC algorithms from O(n3) per sweep to roughly O(n2), where n is the number of particles, and a sweep is a sequence of n steps, each attempting to move a distinct particle. We demonstrate experimentally that we can achieve the improved scaling without increasing statistical errors. Our results show that preconditioned iterative solvers can dramatically reduce the cost of VMC for large(r) systems.

AB - Quantum Monte Carlo (QMC) methods are often used to calculate properties of many body quantum systems. The main cost of many QMC methods, for example, the variational Monte Carlo (VMC) method, is in constructing a sequence of Slater matrices and computing the ratios of determinants for successive Slater matrices. Recent work has improved the scaling of constructing Slater matrices for insulators so that the cost of constructing Slater matrices in these systems is now linear in the number of particles, whereas computing determinant ratios remains cubic in the number of particles. With the long term aim of simulating much larger systems, we improve the scaling of computing the determinant ratios in the VMC method for simulating insulators by using preconditioned iterative solvers. The main contribution of this paper is the development of a method to efficiently compute for the Slater matrices a sequence of preconditioners that make the iterative solver converge rapidly. This involves cheap preconditioner updates, an effective reordering strategy, and a cheap method to monitor instability of incomplete LU decomposition with threshold and pivoting (ILUTP) preconditioners. Using the resulting preconditioned iterative solvers to compute determinant ratios of consecutive Slater matrices reduces the scaling of QMC algorithms from O(n3) per sweep to roughly O(n2), where n is the number of particles, and a sweep is a sequence of n steps, each attempting to move a distinct particle. We demonstrate experimentally that we can achieve the improved scaling without increasing statistical errors. Our results show that preconditioned iterative solvers can dramatically reduce the cost of VMC for large(r) systems.

KW - Krylov subspace methods

KW - Preconditioning

KW - Quantum Monte Carlo

KW - Sequence of linear systems

KW - Updating preconditioners

KW - Variational Monte Carlo

UR - http://www.scopus.com/inward/record.url?scp=80052750602&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=80052750602&partnerID=8YFLogxK

U2 - 10.1137/100805467

DO - 10.1137/100805467

M3 - Article

AN - SCOPUS:80052750602

VL - 33

SP - 1837

EP - 1859

JO - SIAM Journal of Scientific Computing

JF - SIAM Journal of Scientific Computing

SN - 1064-8275

IS - 4

ER -