Characterization of the accuracy of the fast multipole method in particle simulations

DOI10.1002/NME.2611MaRDI QIDQ3649867zbMATHOpenAlexWikidataFDO

Authors Felipe A Cruz, Lorena A. Barba

Publication date 7 December 2009

Published in International Journal for Numerical Methods in Engineering (Search for Journal in Brave)

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

zbMATH Keywords

fast multipole methodparticle methodsvortex methodorder-\(N\) algorithmshierarchical algorithms

Mathematics Subject Classification ID

Particle methods and lattice-gas methods (76M28) Vortex methods applied to problems in fluid mechanics (76M23)

Abstract: The Fast Multipole Method (FMM) offers an acceleration for pairwise interaction calculation, known as $N$-body problems, from $mathcalO(N^2)$ to $mathcalO(N)$ with $N$ particles. This has brought dramatic increase in the capability of particle simulations in many application areas, such as electrostatics, particle formulations of fluid mechanics, and others. Although the literature on the subject provides theoretical error bounds for the FMM approximation, there are not many reports of the measured errors in a suite of computational experiments. We have performed such an experimental investigation, and summarized the results of about 1000 calculations using the FMM algorithm, to characterize the accuracy of the method in relation with the different parameters available to the user. In addition to the more standard diagnostic of the maximum error, we supply illustrations of the spatial distribution of the errors, which offers visual evidence of all the contributing factors to the overall approximation accuracy: multipole expansion, local expansion, hierarchical spatial decomposition (interaction lists, local domain, far domain). This presentation is a contribution to any researcher wishing to incorporate the FMM acceleration to their application code, as it aids in understanding where accuracy is gained or compromised.

Recommendations

• Fast multipole method for particle interactions: an open source parallel library component
• Fast multipole methods for particle dynamics
• A Fast Adaptive Multipole Algorithm for Particle Simulations
• Fast Fourier Transform Accelerated Fast Multipole Algorithm
• scientific article; zbMATH DE number 1064576

Cites work

• A fast algorithm for particle simulations
• A multipole expansion technique in solving boundary integral equations
• Advances in viscous vortex methods?meshless spatial adaption based on radial basis function interpolation
• Billion vortex particle direct numerical simulations of aircraft wakes
• On the Rokhlin-Greengard method with vortex blobs for problems posed in all space or periodic in one direction

Cited in

(5)

• Fast exact evaluation of particle interaction vectors in the finite volume particle method
• PetFMM -- a dynamically load-balancing parallel fast multipole library
• Fast multipole method for particle interactions: an open source parallel library component
• Comparing seven spectral methods for interpolation and for solving the Poisson equation in a disk: Zernike polynomials, Logan-Shepp ridge polynomials, Chebyshev-Fourier series, cylindrical Robert functions, Bessel-Fourier expansions, square-to-disk conformal mapping and radial basis functions
• The rapid assessment for three-dimensional potential model of large-scale particle system by a modified multilevel fast multipole algorithm

Describes a project that uses

Uses Software

• PETSc

This page was built for publication: Characterization of the accuracy of the fast multipole method in particle simulations

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