A Kernel-Independent Treecode Based on Barycentric Lagrange Interpolation (Communications in Computational Physics, 2020)
A kernel-independent treecode (KITC) is presented for fast summation ofparticle interactions. The method employs barycentric Lagrange interpolation atChebyshev points to approximate well-separated particle-cluster interactions. TheKITC requires only kernel evaluations, is suitable for non-oscillatory kernels, and relies on the scale-invariance property of barycentric Lagrange interpolation. For a givenlevel of accuracy, the treecode reduces the operation count for pairwise interactionsfrom $\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, andnumerical results show the treecode performance in terms of error, CPU time, andmemory consumption. The KITC is a relatively simple algorithm with low memoryconsumption, and this enables a straightforward OpenMP parallelization.