next up previous contents
Next: The Continuous Fast Multipole Up: Introduction to Linear Methods Previous: Introduction to Linear Methods

The Fast Multipole Method

The breakthrough was made in 1985 when Greengard and Rokhlin [178,179,180] showed how to compute the Coulomb energy of point charges in only linear work. Greengard's Fast Multipole Method (FMM) belongs to the family of algorithms called tree codes. Tree codes [181] acquire their speed by transforming the information about a cluster of charge into a simpler representation which is used to compute the influence of the cluster on objects at large distances.

The Fast Multipole Method begins by scaling all particles into a box with coordinate ranges $[0 \ldots 1,0 \ldots 1,0 \ldots 1]$ to ensure numerical stability of subsequent operations. The parent box is then divided in half along each Cartesian axis. Each child box is then further subdivided, forming a `computational family tree'. The number of subdivisions is chosen so that the number of particles in the lowest level boxes is approximately independent of the number of particles (this is required to achieve linear scaling).

Each particle is then placed within a box on the lowest level of the tree. Any empty boxes are removed to allow efficiency for inhomogeneous systems. The charges of particles within each lowest level box are then expanded in multipoles about the center of its box. The multipole expansion of each lowest level box is then translated to the center of its parent box via one of three special FMM operators.

The second of the FMMs operators is used for each box to transform the multipole expansions of all well-separated boxes (those that are not nearest neighbours) into Taylor expansions about the center of the current box. However, only those multipole expansions from boxes which are well-separated at the present level and not well-separated at the parent level are interacted. The multipole expansions are also translated to Taylor expansions in the parent box. This allows each transformation to be performed as high up the tree as possible. In practice this pass is the bottleneck of the algorithm, yet, like all the other passes, it is O(N).

The third pass transforms the parent Taylor expansions down the tree to the child boxes, so that each low-level box contains the Taylor expansion representing all well-separated particles. The fourth pass calculates the far-field potential for each particle via the Taylor representation in the particles box. A final pass calculates the interactions between particles that are not well-separated at any level in the tree.


next up previous contents
Next: The Continuous Fast Multipole Up: Introduction to Linear Methods Previous: Introduction to Linear Methods
Ross D. Adamson
1999-01-27