Multibody multipole methods

DOI10.1016/J.JCP.2012.06.027MaRDI QIDQ2446916zbMATH OpenOpenAlexFDO

Authors Dongryeol Lee, Arkadas Ozakin, Alexander Gray

Publication date 23 April 2014

Published in Journal of Computational Physics (Search for Journal in Brave)

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

zbMATH Keywords

Axilrod-Teller potentialdata structuresfast multipole methodskd-treesmulti-tree algorithms

Mathematics Subject Classification ID

Approximation methods and numerical treatment of dynamical systems (37M99) Complexity and performance of numerical algorithms (65Y20) (n)-body problems (70F10) Einstein-Maxwell equations (83C22)

Abstract: A three-body potential function can account for interactions among triples of particles which are uncaptured by pairwise interaction functions such as Coulombic or Lennard-Jones potentials. Likewise, a multibody potential of order $n$ can account for interactions among $n$-tuples of particles uncaptured by interaction functions of lower orders. To date, the computation of multibody potential functions for a large number of particles has not been possible due to its $O(N^n)$ scaling cost. In this paper we describe a fast tree-code for efficiently approximating multibody potentials that can be factorized as products of functions of pairwise distances. For the first time, we show how to derive a Barnes-Hut type algorithm for handling interactions among more than two particles. Our algorithm uses two approximation schemes: 1) a deterministic series expansion-based method; 2) a Monte Carlo-based approximation based on the central limit theorem. Our approach guarantees a user-specified bound on the absolute or relative error in the computed potential with an asymptotic probability guarantee. We provide speedup results on a three-body dispersion potential, the Axilrod-Teller potential.

Recommendations

• Publication:3359807
• A treecode for potentials of the formr^−λ
• scientific article; zbMATH DE number 4080996
• Improving Error Bounds for Multipole-Based Treecodes
• Publication:4860163

Cites work

• A fast adaptive multipole algorithm in three dimensions
• A kernel-independent adaptive fast multipole algorithm in two and three dimensions
• A new version of the fast multipole method for screened Coulomb interactions in three dimensions
• An Accelerated Kernel-Independent Fast Multipole Method in One Dimension
• An Implementation of the Fast Multipole Method without Multipoles
• Fast kernel conditional density estimation: a dual-tree Monte Carlo approach
• scientific article; zbMATH DE number 2088276 (Why is no real title available?)
• Modified force decomposition algorithms for calculating three-body interactions via molecular dynamics
• Multidimensional binary search trees used for associative searching
• The Fast Gauss Transform

Cited in

(12)

• Three-body dispersion potentials involving electric octupole coupling
• A graph-based N-body approximation with application to stochastic neighbor embedding
• scientific article; zbMATH DE number 1728488 (Why is no real title available?)
• THE MULTIPLE MULTIPOLE METHOD (MMP)
• scientific article; zbMATH DE number 4213512 (Why is no real title available?)
• Multipole structure and coordinate systems
• Outer inverses and multi body system simulation
• scientific article; zbMATH DE number 833680 (Why is no real title available?)
• A treecode for potentials of the formr^−λ
• The method of ordered multiple interactions for closed bodies
• Proximate computation N-body problem by analytic function in dense domain and sparse domain
• Fast relative approximation of potential fields.

This page was built for publication: Multibody multipole methods

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