Hermite Interpolation in the Treecode Algorithm

Abstract

In this thesis, a treecode implementing Hermite interpolation is constructed to approximate a summation of pairwise interactions on large data sets. Points are divided into a hierarchical tree structure and the interactions between points and well-separated clusters are approximated by interpolating the kernel function over the cluster. Performing the direct summation takes O(N^2) time for system size N, and evidence is presented to show the method presented in this paper scales with O(N logN) time. Comparisons between this method and existing ones are made, highlighting the relative simplicity and adaptability of this process. Parallelization of the computational step is implemented by splitting the data set into pieces whose interactions are independently calculated on separate CPU cores. Additionally, steps are taken to make this approximation more efficient, allowing greater precision to be achieved without increasing completion time. Results are presented for the 3D 1/r and Screened Coulomb Potential exp(-kr)/r kernels on random data sets in size up to 10^7.