## Algorithm 967

 swMATH ID: 23693 Software Authors: Malhotra, Dhairya; Biros, George Description: Algorithm 967: a distributed-memory fast multipole method for volume potentials. The solution of a constant-coefficient 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 low-frequency 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 high-order piecewise Chebyshev polynomials and an octree data structure to represent the input and output fields and enable spectrally accurate approximation of the near-field and the Kernel Independent FMM (KIFMM) for the far-field approximation. For distributed-memory parallelism, we use space-filling curves, locally essential trees, and a hypercube-like 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; near-field; far-field; 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 distributed-memory fast multipole method for volume potentials. Zbl 1371.65125
Malhotra, Dhairya; Biros, George
2016
all top 5

### Cited by 15 Authors

 2 Krasny, Robert 2 Tlupova, Svetlana 2 Wang, Lei 1 Abduljabbar, Mustafa 1 Al Farhan, Mohammed 1 Al-Harthi, Noha 1 Bağci, Hakan 1 Biros, George 1 Chen, Rui 1 Greengard, Leslie F. 1 Malhotra, Dhairya 1 Shelley, Michael J. 1 Wang, Jun 1 Yan, Wen 1 Yokota, Rio

### Cited in 5 Serials

 2 SIAM Journal on Scientific Computing 1 Journal of Computational Physics 1 ACM Transactions on Mathematical Software 1 Communications in Computational Physics 1 Advances in Applied Mathematics and Mechanics

### Cited in 5 Fields

 6 Numerical analysis (65-XX) 2 Partial differential equations (35-XX) 2 Fluid mechanics (76-XX) 1 Mechanics of particles and systems (70-XX) 1 Optics, electromagnetic theory (78-XX)