Optimal partitions for the fast multipole method

Abstract

The fast multipole method is an algorithm first developed to approximately solve the N-body problem in linear time. Part of the FMM involves recursively partitioning a region of source points into cells. Insight from studying lattices and covering problems leads to new, more efficient partitions for the FMM. New partitions are designed to reduce near-field and far-field calculations. Results from simulations show significant computation time reduction with little to no additional error in many cases.