The Fast Multipole Algorithm ( FMA) of Greengard and Rokhlin [26,27]
has been successfully used for efficiently computing the N-body problem for a single (non-periodic)
cell.
The main feature of the FMA is that it offers a solution to the traditional 
N-body problem that is linear in N in many cases (and never worse than 
while maintaining known accuracy bounded by rigorously derived error bounds.
Many applications have capitalized on the FMA's performance, especially in molecular dynamics and
celestial mechanics.
The basic idea behind FMA is simple. The force (potential) exerted on a particle due to all the pair-wise interactions can be divided into two components: one due to nearby particles that can be computed directly and one due to the distant particles approximated by their multipole expansions.
Given a collection of point charges 
, Fig.(5),
enclosed by a sphere of radius a whose
center is a distance r away such that r > a , the potential
at P due to
all the well separated particles 
is given by the infinite multipole expansion:
where 
is the spherical harmonic polynomial [32], and
Figure 5: The multipole expansion principle.
In a system of charged particles, the FMA starts by using hierarchical spatial decomposition (typically an oct-tree) to divide the simulation cell into smaller sub-cells. A truncated multipole expansion is then calculated for each sub-cell at the finest refinement level which expresses the effect of all particles in that sub-cell on distant particles. These expansions are combined in a hierarchical fashion to represent the effects of larger and larger groups of particles in what is known as the upward pass. The far-field potential at the center of a sub-cell due to particles of another sub-cell that is sufficiently far apart is computed via a Taylor (local) expansion that utilizes the multipole expansion of the distant sub-cell. As distant sub-cells interact, each sub-cell accumulates the far-field effects into a single local Taylor expansion. In the downward pass, the local expansions are used to transfer the field effect from parent to children sub-cells in a non-redundant procedure. Finally, far-field effects are combined with direct short-field evaluations to yield the potential at each particle. For more details, the reader is referred to [26,27], and [9,10] for FMA's 3-D parallel implementation. It is worth noting that any other converging series approximation of the potential due to the far cells can be used in place of multipoles. Anderson [4], for example, used a ``ring'' (``sphere'' in 3-D) approximation whereby the induced potential of a group of charged particles is approximated over certain locations on the circumference of a surrounding ring.
In the FMA, there are several translations used to facilitate computing the electrostatics. To calculate the multipole expansion at the lowest level of spatial decomposition equations (30) and (31) are used which represent the aggregate potential due to the k particles. Similar multipole expansions are carried out for all cells at all levels using the Multipole to Multipole translational property, as shown in Fig.(6).
Figure 6: The Fast Multipole Algorithm mechanisms: (a,b) after spatial decomposition, the child cells
use the Multipole to Multipole translation to shift their multipole expansion to the
center of the parent cell, (c) using the Multipole to Local translation, well-separated cells interact
by creating a local expansion at the center of cell B due to cell A, (d) the children of cell B
feel the potential of cell A by using the Local to Local translation to shift the parent's (cell B) local
expansion.
Cell-to-cell interactions are carried out between well-separated cells using Multipole to Local translations. In the final step, each parent cell passes down its accumulative far-field interaction to each of its children using the Local to Local translation.
We have so far introduced FMA for the simulation of isolated systems, i.e. free boundary conditions. However, the fast multipole method has been extended for use with periodic boundary conditions. Schmidt and Lee [44] have developed a method to simulate point-charge systems with infinite PBC in three dimensions in a procedure that uses both FMA and Ewald techniques. Given a charge-neutral system, all multipole and local expansions at all refinement levels of the basic unit cell are calculated and the potential due to all particles in the unit cell is obtained. A multipole expansion approximation is now available for the original unit cell as well as the image cells. This is based on the fact that all image cells have the same multipole expansion as the basic unit cell with respect to their centers. The local expansions of all periodic image cells, except the nearest neighbors (26 cells), are next used to evaluate the local expansion at the basic unit cell. However, to obtain the local expansion of the image cells, the multipole to local translation is expressed using an Ewald sum formulation. The algorithm next proceeds with its downward pass and terminates by taking the sum over all image cells using a recursive formulation of the Ewald sum.
In their paper, Schmidt and Lee [44] presented
a timing and accuracy comparison between their FMA implementation of PBC and Ewald summation.
It is not clear however, where the break even point is, i.e. the number of
particles at which both methods are equally fast, as both implementations have not been optimized
(by authors admission). Therefore, the only conclusion to be made about the efficiency of their
implementation regards the marginal overhead of doing PBC over a single unit cell, roughly 
.
