Multithreading in adaptive fast multipole methods

Abstract: It has been shown that fast multipole methods can achieve good scalability on multi-core architectures. We have for an adaptive single-threaded fast multipole method implemented multithreading support via the OpenMP API. The downward- and upward pass in the fast multipole method are parallelized, and the multithreaded implementation achieves on a quad-core architecture for uniform distributions a 6.6x speedup and a non-uniform distribution a 4.2x speedup. The lower speedup for the non-uniform distributions results from poor load balancing caused by higher variance in connectivity. We conclude that future research in how connectivity affects parallel performance is needed.