Fast Multipole Method

The Fast Multipole Method is a linear scaling algorithm to account for pairwise interactions in systems governed by the inverse distance function. It performs a binary tree decomposition of space into a hierarchical set of boxes and introduces the well separation criterion, and the concepts of near and far fields. After initialization, the method computes the multipole expansions for the boxes located in the lowest-level hierarchy, then performs an upward translation of the multipole expansion from the child boxes to their parents, collecting far field contributions in the appropriate hierarchy levels, and concludes the operation flow by performing a downward translation of the computed irregular multipole expansions from the parent back to the child boxes, so that each box at the lowest-level hierarchy receives the electrostatic effect of all remote boxes. This chapter explains the near-field and far-field box counts, provides a proof of the linear scaling of the various steps and of the energy computation in the near field, and derives a formula that combines the error bound with the well separation parameter, box side length, and expansion truncation parameter. Within this formula, the value of any variable can be defined in terms of the other three.