A Kernel-Independent Treecode Based on Barycentric Lagrange Interpolation
A Kernel-Independent Treecode Based on Barycentric Lagrange Interpolation
复制标题
DOI：
10.4208/cicp.oa-2019-0177
复制
发表时间：
2019-02
影响因子：
3.7
通讯作者：
Lei Wang;R. Krasny;Svetlana Tlupova
中科院分区：
文献类型：
--
作者：
Lei Wang;R. Krasny;Svetlana Tlupova
提出了一种与核无关的树码（KITC），用于粒子对相互作用的快速求和。一般来说，树码用粒子簇相互作用代替粒子簇相互作用，这里我们利用切比雪夫点的质心拉格朗日插值来计算分离良好的粒子簇相互作用。该方案只需要核计算，适用于非振荡核。对于给定的精度水平，树码将成对相互作用的操作计数从$O(N^2)$减少到$O(N \log N)$，其中$N$是系统中的粒子数。该算法在正则化stokeslet和rotlet系统的三维串行和并行仿真中得到了验证，数值结果显示了该算法在误差、CPU时间和内存开销方面的性能。KITC是一种相对简单的算法，具有较低的内存开销，这可以实现直接有效的并行化。
A kernel-independent treecode (KITC) is presented for fast summation of pairwise particle interactions. In general, treecodes replace the particle-particle interactions by particle-cluster interactions, and here we utilize barycentric Lagrange interpolation at Chebyshev points to compute well-separated particle-cluster interactions. The scheme requires only kernel evaluations and is suitable for non-oscillatory kernels. For a given level of accuracy, the treecode reduces the operation count for pairwise interactions from $O(N^2)$ to $O(N \log N)$, where $N$ is the number of particles in the system. The algorithm is demonstrated in serial and parallel simulations for systems of regularized Stokeslets and rotlets in 3D, and numerical results show the treecode performance in terms of error, CPU time, and memory overhead. The KITC is a relatively simple algorithm with low memory overhead, and this enables a straightforward efficient parallelization.