Parallel cross interpolation for high-precision calculation of high-dimensional integrals

Sergey Dolgov, Dmitry Savostyanov

Research output: Contribution to journalArticleResearchpeer-review

Abstract

We propose a parallel version of the cross interpolation algorithm and apply it to calculate high-dimensional integrals motivated by Ising model in quantum physics. In contrast to mainstream approaches, such as Monte Carlo and quasi Monte Carlo, the samples calculated by our algorithm are neither random nor form a regular lattice. Instead we calculate the given function along individual dimensions (modes) and use these values to reconstruct its behaviour in the whole domain. The positions of the calculated univariate fibres are chosen adaptively for the given function. The required evaluations can be executed in parallel along each mode (variable) and over all modes.

To demonstrate the efficiency of the proposed method, we apply it to compute high-dimensional Ising susceptibility integrals, arising from asymptotic expansions for the spontaneous magnetisation in two-dimensional Ising model of ferromagnetism. We observe strong superlinear convergence of the proposed method, while the MC and qMC algorithms converge sublinearly. Using multiple precision arithmetic, we also observe exponential convergence of the proposed algorithm. Combining high-order convergence, almost perfect scalability up to hundreds of processes, and the same flexibility as MC and qMC, the proposed algorithm can be a new method of choice for problems involving high-dimensional integration, e.g. in statistics, probability, and quantum physics.
Original languageEnglish
Article number106869
JournalComputer Physics Communications
Volume246
DOIs
Publication statusPublished - 23 Aug 2019

Fingerprint

interpolation
Ising model
physics
ferromagnetism
flexibility
statistics
magnetic permeability
magnetization
expansion
fibers
evaluation

Bibliographical note

© 2019 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY license
(http://creativecommons.org/licenses/by/4.0/)

Keywords

  • Cross interpolation
  • High precision
  • High-dimensional integration
  • Ising integrals
  • Parallel algorithms
  • Tensor train format

Cite this

@article{bce58d1337844f0bb64b67581a981f0c,
title = "Parallel cross interpolation for high-precision calculation of high-dimensional integrals",
abstract = "We propose a parallel version of the cross interpolation algorithm and apply it to calculate high-dimensional integrals motivated by Ising model in quantum physics. In contrast to mainstream approaches, such as Monte Carlo and quasi Monte Carlo, the samples calculated by our algorithm are neither random nor form a regular lattice. Instead we calculate the given function along individual dimensions (modes) and use these values to reconstruct its behaviour in the whole domain. The positions of the calculated univariate fibres are chosen adaptively for the given function. The required evaluations can be executed in parallel along each mode (variable) and over all modes.To demonstrate the efficiency of the proposed method, we apply it to compute high-dimensional Ising susceptibility integrals, arising from asymptotic expansions for the spontaneous magnetisation in two-dimensional Ising model of ferromagnetism. We observe strong superlinear convergence of the proposed method, while the MC and qMC algorithms converge sublinearly. Using multiple precision arithmetic, we also observe exponential convergence of the proposed algorithm. Combining high-order convergence, almost perfect scalability up to hundreds of processes, and the same flexibility as MC and qMC, the proposed algorithm can be a new method of choice for problems involving high-dimensional integration, e.g. in statistics, probability, and quantum physics.",
keywords = "Cross interpolation, High precision, High-dimensional integration, Ising integrals, Parallel algorithms, Tensor train format",
author = "Sergey Dolgov and Dmitry Savostyanov",
note = "{\circledC} 2019 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/)",
year = "2019",
month = "8",
day = "23",
doi = "10.1016/j.cpc.2019.106869",
language = "English",
volume = "246",
journal = "Computer Physics Communications",
issn = "0010-4655",

}

Parallel cross interpolation for high-precision calculation of high-dimensional integrals. / Dolgov, Sergey; Savostyanov, Dmitry.

In: Computer Physics Communications, Vol. 246, 106869, 23.08.2019.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Parallel cross interpolation for high-precision calculation of high-dimensional integrals

AU - Dolgov, Sergey

AU - Savostyanov, Dmitry

N1 - © 2019 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/)

PY - 2019/8/23

Y1 - 2019/8/23

N2 - We propose a parallel version of the cross interpolation algorithm and apply it to calculate high-dimensional integrals motivated by Ising model in quantum physics. In contrast to mainstream approaches, such as Monte Carlo and quasi Monte Carlo, the samples calculated by our algorithm are neither random nor form a regular lattice. Instead we calculate the given function along individual dimensions (modes) and use these values to reconstruct its behaviour in the whole domain. The positions of the calculated univariate fibres are chosen adaptively for the given function. The required evaluations can be executed in parallel along each mode (variable) and over all modes.To demonstrate the efficiency of the proposed method, we apply it to compute high-dimensional Ising susceptibility integrals, arising from asymptotic expansions for the spontaneous magnetisation in two-dimensional Ising model of ferromagnetism. We observe strong superlinear convergence of the proposed method, while the MC and qMC algorithms converge sublinearly. Using multiple precision arithmetic, we also observe exponential convergence of the proposed algorithm. Combining high-order convergence, almost perfect scalability up to hundreds of processes, and the same flexibility as MC and qMC, the proposed algorithm can be a new method of choice for problems involving high-dimensional integration, e.g. in statistics, probability, and quantum physics.

AB - We propose a parallel version of the cross interpolation algorithm and apply it to calculate high-dimensional integrals motivated by Ising model in quantum physics. In contrast to mainstream approaches, such as Monte Carlo and quasi Monte Carlo, the samples calculated by our algorithm are neither random nor form a regular lattice. Instead we calculate the given function along individual dimensions (modes) and use these values to reconstruct its behaviour in the whole domain. The positions of the calculated univariate fibres are chosen adaptively for the given function. The required evaluations can be executed in parallel along each mode (variable) and over all modes.To demonstrate the efficiency of the proposed method, we apply it to compute high-dimensional Ising susceptibility integrals, arising from asymptotic expansions for the spontaneous magnetisation in two-dimensional Ising model of ferromagnetism. We observe strong superlinear convergence of the proposed method, while the MC and qMC algorithms converge sublinearly. Using multiple precision arithmetic, we also observe exponential convergence of the proposed algorithm. Combining high-order convergence, almost perfect scalability up to hundreds of processes, and the same flexibility as MC and qMC, the proposed algorithm can be a new method of choice for problems involving high-dimensional integration, e.g. in statistics, probability, and quantum physics.

KW - Cross interpolation

KW - High precision

KW - High-dimensional integration

KW - Ising integrals

KW - Parallel algorithms

KW - Tensor train format

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

U2 - 10.1016/j.cpc.2019.106869

DO - 10.1016/j.cpc.2019.106869

M3 - Article

VL - 246

JO - Computer Physics Communications

JF - Computer Physics Communications

SN - 0010-4655

M1 - 106869

ER -