Algorithm 967
swMATH ID:  23693 
Software Authors:  Malhotra, Dhairya; Biros, George 
Description:  Algorithm 967: a distributedmemory fast multipole method for volume potentials. The solution of a constantcoefficient elliptic partial differential equation (PDE) can be computed using an integral transform: A convolution with the fundamental solution of the PDE, also known as a volume potential. We present a fast multipole method (FMM) for computing volume potentials and use them to construct spatially adaptive solvers for the Poisson, Stokes, and lowfrequency Helmholtz problems. Conventional \(N\)body methods apply to discrete particle interactions. With volume potentials, one replaces the sums with volume integrals. Particle \(N\)body methods can be used to accelerate such integrals. but it is more efficient to develop a special FMM. In this article, we discuss the efficient implementation of such an FMM. We use highorder piecewise Chebyshev polynomials and an octree data structure to represent the input and output fields and enable spectrally accurate approximation of the nearfield and the Kernel Independent FMM (KIFMM) for the farfield approximation. For distributedmemory parallelism, we use spacefilling curves, locally essential trees, and a hypercubelike communication scheme developed previously in our group. We present new near and far interaction traversals that optimize cache usage. Also, unlike particle \(N\)body codes, we need a 2:1 balanced tree to allow for precomputations. We present a fast scheme for 2:1 balancing. Finally, we use vectorization, including the AVX instruction set on the Intel Sandy Bridge architecture to get better than 50 
Homepage:  https://dl.acm.org/citation.cfm?doid=2988256.2898349 
Keywords:  \(N\)body problems; potential theory; elliptic partial differential equation; fundamental solution; fast multipole method; Poisson; Stokes; Helmholtz; discrete particle interactions; nearfield; farfield; parallelism 
Related Software:  ScalFMM; pvfmm; TABI; GitHub; exafmm; ASKIT; Chebfun; FMM3D; HOT; ViennaCL; Trilinos; PETSc; HykSort; GADGET; p4est; PPM 
Cited in:  6 Publications 
Standard Articles
1 Publication describing the Software, including 1 Publication in zbMATH  Year 

Algorithm 967: A distributedmemory fast multipole method for volume potentials. Zbl 1371.65125 Malhotra, Dhairya; Biros, George 
2016

all
top 5
Cited by 15 Authors
Cited in 5 Serials
Cited in 5 Fields
6  Numerical analysis (65XX) 
2  Partial differential equations (35XX) 
2  Fluid mechanics (76XX) 
1  Mechanics of particles and systems (70XX) 
1  Optics, electromagnetic theory (78XX) 