full
search.png

Search

close.png

Cancel

arrow
Volume 28, Issue 4
A Kernel-Independent Treecode Based on Barycentric Lagrange Interpolation

Lei Wang, Robert Krasny & Svetlana Tlupova

DOI: 10.4208/cicp.OA-2019-0177

Commun. Comput. Phys., 28 (2020), pp. 1415-1436.

Published online: 2020-08

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

Preview Full PDF 3280 41419

Cited by

google scholar semantic scholar
Export citation
  • Abstract

A kernel-independent treecode (KITC) is presented for fast summation of particle interactions. The method employs barycentric Lagrange interpolation at Chebyshev points to approximate well-separated particle-cluster interactions. The KITC requires only kernel evaluations, is suitable for non-oscillatory kernels, and relies on the scale-invariance property of barycentric Lagrange interpolation. For a given level of accuracy, the treecode reduces the operation count for pairwise interactions from $\mathcal{O}$($N^2$) to $\mathcal{O}$($N$log$N$), where $N$ is the number of particles in the system. The algorithm is demonstrated for systems of regularized Stokeslets and rotlets in 3D, and numerical results show the treecode performance in terms of error, CPU time, and memory consumption. The KITC is a relatively simple algorithm with low memory consumption, and this enables a straightforward OpenMP parallelization.

  • Keywords

Treecode, barycentric Lagrange interpolation, scale-invariance, Chebyshev points, regularized Stokeslets.

  • AMS Subject Headings

65D99, 76D07

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address
  • BibTex
  • RIS
  • TXT
@Article{CiCP-28-1415, author = {Wang , LeiKrasny , Robert and Tlupova , Svetlana}, title = {A Kernel-Independent Treecode Based on Barycentric Lagrange Interpolation}, journal = {Communications in Computational Physics}, year = {2020}, volume = {28}, number = {4}, pages = {1415--1436}, abstract = {

A kernel-independent treecode (KITC) is presented for fast summation of particle interactions. The method employs barycentric Lagrange interpolation at Chebyshev points to approximate well-separated particle-cluster interactions. The KITC requires only kernel evaluations, is suitable for non-oscillatory kernels, and relies on the scale-invariance property of barycentric Lagrange interpolation. For a given level of accuracy, the treecode reduces the operation count for pairwise interactions from $\mathcal{O}$($N^2$) to $\mathcal{O}$($N$log$N$), where $N$ is the number of particles in the system. The algorithm is demonstrated for systems of regularized Stokeslets and rotlets in 3D, and numerical results show the treecode performance in terms of error, CPU time, and memory consumption. The KITC is a relatively simple algorithm with low memory consumption, and this enables a straightforward OpenMP parallelization.

}, issn = {1991-7120}, doi = {https://doi.org/10.4208/cicp.OA-2019-0177}, url = {http://global-sci.org/intro/article_detail/cicp/18106.html} }
TY - JOUR T1 - A Kernel-Independent Treecode Based on Barycentric Lagrange Interpolation AU - Wang , Lei AU - Krasny , Robert AU - Tlupova , Svetlana JO - Communications in Computational Physics VL - 4 SP - 1415 EP - 1436 PY - 2020 DA - 2020/08 SN - 28 DO - http://doi.org/10.4208/cicp.OA-2019-0177 UR - https://global-sci.org/intro/article_detail/cicp/18106.html KW - Treecode, barycentric Lagrange interpolation, scale-invariance, Chebyshev points, regularized Stokeslets. AB -

A kernel-independent treecode (KITC) is presented for fast summation of particle interactions. The method employs barycentric Lagrange interpolation at Chebyshev points to approximate well-separated particle-cluster interactions. The KITC requires only kernel evaluations, is suitable for non-oscillatory kernels, and relies on the scale-invariance property of barycentric Lagrange interpolation. For a given level of accuracy, the treecode reduces the operation count for pairwise interactions from $\mathcal{O}$($N^2$) to $\mathcal{O}$($N$log$N$), where $N$ is the number of particles in the system. The algorithm is demonstrated for systems of regularized Stokeslets and rotlets in 3D, and numerical results show the treecode performance in terms of error, CPU time, and memory consumption. The KITC is a relatively simple algorithm with low memory consumption, and this enables a straightforward OpenMP parallelization.

Wang , LeiKrasny , Robert and Tlupova , Svetlana. (2020). A Kernel-Independent Treecode Based on Barycentric Lagrange Interpolation. Communications in Computational Physics. 28 (4). 1415-1436. doi:10.4208/cicp.OA-2019-0177
Copy to clipboard
BibteX RIS TXT
The citation has been copied to your clipboard