Improving Error Bounds for Multipole-Based Treecodes

. Rapid evaluation of potentials in particle systems is an important, time-consuming step in many physical simulations. Over the past decade, the development of treecodes such as the Fast Multipole method and Barnes-Hut method has enabled large scale simulations in astrophysics, molecular dynamics, material science, etc. These methods use fixed-degree polynomial approximations for the potential at a point due to a set of particles in a hierarchical representation of the particle system. In this paper, we present analysis and experiments to illustrate that fixed-degree multipole approximations can lead to large aggregate errors. We describe an alternate strategy based on careful selection of the multipole degree that leads to asymptotically lower errors, while incurring minimal computation overhead. First, we estimate the error associated with each particle-cluster interaction and the aggregate error for each particle. Then we describe a technique for computing the multipole degree of e..