arrow
Volume 18, Issue 3
PVFMM: A Parallel Kernel Independent FMM for Particle and Volume Potentials

Dhairya Malhotra & George Biros

Commun. Comput. Phys., 18 (2015), pp. 808-830.

Published online: 2018-04

[An open-access article; the PDF is free to any online user.]

Export citation
  • Abstract

We describe our implementation of a parallel fast multipole method for evaluating potentials for discrete and continuous source distributions. The first requires summation over the source points and the second requiring integration over a continuous source density. Both problems require $\mathcal{O}$($N^2$) complexity when computed directly; however, can be accelerated to $\mathcal{O}$($N$) time using FMM. In our PVFMM software library, we use kernel independent FMM and this allows us to compute potentials for a wide range of elliptic kernels. Our method is high order, adaptive and scalable. In this paper, we discuss several algorithmic improvements and performance optimizations including cache locality, vectorization, shared memory parallelism and use of coprocessors. Our distributed memory implementation uses space-filling curve for partitioning data and a hypercube communication scheme. We present convergence results for Laplace, Stokes and Helmholtz (low wavenumber) kernels for both particle and volume FMM. We measure efficiency of our method in terms of CPU cycles per unknown for different accuracies and different kernels. We also demonstrate scalability of our implementation up to several thousand processor cores on the Stampede platform at the Texas Advanced Computing Center.

  • Keywords

  • AMS Subject Headings

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address
  • BibTex
  • RIS
  • TXT
@Article{CiCP-18-808, author = {}, title = {PVFMM: A Parallel Kernel Independent FMM for Particle and Volume Potentials}, journal = {Communications in Computational Physics}, year = {2018}, volume = {18}, number = {3}, pages = {808--830}, abstract = {

We describe our implementation of a parallel fast multipole method for evaluating potentials for discrete and continuous source distributions. The first requires summation over the source points and the second requiring integration over a continuous source density. Both problems require $\mathcal{O}$($N^2$) complexity when computed directly; however, can be accelerated to $\mathcal{O}$($N$) time using FMM. In our PVFMM software library, we use kernel independent FMM and this allows us to compute potentials for a wide range of elliptic kernels. Our method is high order, adaptive and scalable. In this paper, we discuss several algorithmic improvements and performance optimizations including cache locality, vectorization, shared memory parallelism and use of coprocessors. Our distributed memory implementation uses space-filling curve for partitioning data and a hypercube communication scheme. We present convergence results for Laplace, Stokes and Helmholtz (low wavenumber) kernels for both particle and volume FMM. We measure efficiency of our method in terms of CPU cycles per unknown for different accuracies and different kernels. We also demonstrate scalability of our implementation up to several thousand processor cores on the Stampede platform at the Texas Advanced Computing Center.

}, issn = {1991-7120}, doi = {https://doi.org/10.4208/cicp.020215.150515sw}, url = {http://global-sci.org/intro/article_detail/cicp/11049.html} }
TY - JOUR T1 - PVFMM: A Parallel Kernel Independent FMM for Particle and Volume Potentials JO - Communications in Computational Physics VL - 3 SP - 808 EP - 830 PY - 2018 DA - 2018/04 SN - 18 DO - http://doi.org/10.4208/cicp.020215.150515sw UR - https://global-sci.org/intro/article_detail/cicp/11049.html KW - AB -

We describe our implementation of a parallel fast multipole method for evaluating potentials for discrete and continuous source distributions. The first requires summation over the source points and the second requiring integration over a continuous source density. Both problems require $\mathcal{O}$($N^2$) complexity when computed directly; however, can be accelerated to $\mathcal{O}$($N$) time using FMM. In our PVFMM software library, we use kernel independent FMM and this allows us to compute potentials for a wide range of elliptic kernels. Our method is high order, adaptive and scalable. In this paper, we discuss several algorithmic improvements and performance optimizations including cache locality, vectorization, shared memory parallelism and use of coprocessors. Our distributed memory implementation uses space-filling curve for partitioning data and a hypercube communication scheme. We present convergence results for Laplace, Stokes and Helmholtz (low wavenumber) kernels for both particle and volume FMM. We measure efficiency of our method in terms of CPU cycles per unknown for different accuracies and different kernels. We also demonstrate scalability of our implementation up to several thousand processor cores on the Stampede platform at the Texas Advanced Computing Center.

Dhairya Malhotra & George Biros. (2020). PVFMM: A Parallel Kernel Independent FMM for Particle and Volume Potentials. Communications in Computational Physics. 18 (3). 808-830. doi:10.4208/cicp.020215.150515sw
Copy to clipboard
The citation has been copied to your clipboard