The fast multipole method in the differential algebra framework

A method is presented that allows the computation of space charge effects of arbitrary and large distributions of particles in an efficient and accurate way based on a variant of the Fast Multipole Method (FMM). It relies on an automatic multigrid-based decomposition of charges in near and far regions and the use of high-order differential algebra methods to obtain decompositions of far fields that lead to an error that scales with a high power of the order. Given an ensemble of N particles, the method allows the computation of the self-fields of all particles on each other with a computational expense that scales as O(N). Using remainder-enhanced DA methods, it is also possible to obtain rigorous estimates of the errors of the methods. Furthermore, the method allows the computation of all high-order multipoles of the space charge fields that are necessary for the computation of high-order transfer maps and all resulting aberrations. (C) 2011 Elsevier B.V. All rights reserved.