The Cell Multipole Method (CMM) [1] was developed to overcome these
limitations in handling long-range power-law forces in molecular systems. In
particular, it can be used to handle the *R*^-1 (or
*R*^-2 if screened) Coulomb interaction and the
*R*^-6 attractive portion of the usual Lennard-Jones 12-6 or the
exponential-6 van der Waals potentials. It is a true
*O*(*N*)-operation algorithm [2], with substantially better accuracy
than cutoff methods of the same speed. It is thus the most suitable method for
handling large-scale molecular mechanics problems.

The key feature of the CMM and other multipole methods [3,4,5,6] is that they replace the effects of atoms with multipole expansions representing the fields due to those atoms. This replacement reduces the number of computations that must be performed, while not ignoring these effects altogether as in cutoff methods. In order to maintain accuracy, stronger, nearby interactions are represented more accurately than weaker, more distant interactions.

Computing and using these multipole expansions is the major computational task in all multipole methods. The CMM is a particularly regular, easily parallelizable multipole method that enables this task to be performed efficiently. It uses Cartesian coordinates only, unlike the other fast multipole formulations that use spherical harmonics [5,6,7], further simplifying the method. We can divide the CMM into four parts:

- Octree decomposition.
- The space occupied by the system of interest is divided into cells that form a tree. Each cell's effects will be represented by multipole expansions.
- Multipole expansion computation.
- The multipole expansions are computed for each cell at each level within the tree, starting from the leaves, or smallest cells, and working upwards in the tree to the root, which represents the entire system.
- Taylor series expansion computation.
- The multipoles represent the effects of atoms within a given cell. What we require, however, is the effect on an atom within a cell of all the other atoms in the system. We represent the long-range component of this effect with a Taylor series expansion that applies to all atoms within a given cell. The coefficients of this series are computed from the multipoles from the previous step, starting at the root of the tree and working downwards to the leaves.
- Farfield and nearfield computation.
- Once the Taylor series expansion coefficients have been computed for each leaf cell, the force on each atom can be computed as a combination of the effects represented by the Taylor series, evaluated at the atom's location, and the effects of nearby atoms, which are calculated explicitly.

Figure 3-1 shows a two-dimensional projection of some of the cells in the octree. The bounding box has been divided into level 1 cells, one of which has been further subdivided into level 2 cells. A level 2 cell has in turn been split into level 3 cells. All of the level 1 and level 2 cells would be subdivided in this fashion.

(1)

where and are the charge, dipole, and quadrupole moments, respectively; ; is the position of the atom; is the position of the center of the expansion; the power-law for the energy is ; and .

(2)

Another possible alternative is to use a weighted average of the atom locations, with the weights being, for example, the absolute values of the charges on the atoms. This tends to place the center close to atoms with large charges, which will again tend to reduce the higher-order multipole coefficients.

The centroids or weighted averages can easily be computed in a hierarchical fashion using the existing cell tree, as the centroid of a higher level cell is equal to the weighted average of the centroids of its children, where the weights are the number of atoms in each child cell.

We have found that the increased accuracy from the centroid formulation allows the use of more highly truncated expansions than would otherwise be required. Further details are given in chapter 7.

(3)

where .

This process continues up the tree until the root (level 0 cell) is reached. At this point, every cell in the system has associated with it a multipole expansion representing the field due to all of the atoms contained within the cell.

A Taylor series expansion of the farfield for a given cell is used to enable the computation of the farfield at any point within the cell. The coefficients of this expansion are determined from the multipole expansions computed in the previous step.

We define the Taylor series expansion of the field at the position of an atom to be

(4)

where and are the zeroth, first, and second order expansion coefficients, respectively. The centers used for the Taylor series expansion are the same as those used for the multipole expansion.

Figure 3-2. Neighbors and PNCs for a level 3 cell.

To start this process, note that all cells at level 1 (the first set of eight child cells) are immediate neighbors of each other, and thus there is no farfield contribution from the parent or the PNCs of these cells.

By induction, we can continue generating Taylor expansions all the way to the leaf cells, at which point every cell has a Taylor expansion representing the farfield within the cell.

We define the following useful terms:

(5)

The contributions from each PNC to a cell's Taylor expansion coefficients are then:

(6)

(7)

(8)

(9)

where the multipole expansion coefficients are those of the PNC.

The contributions from the parent cell's Taylor series coefficients to one of its child cells' coefficients are:

(10)

where here and the coefficients on the right are from the parent cell.

Since the farfield changes much more slowly than the nearfield, we have found it feasible to perform the farfield calculation at intervals instead of every timestep. The centers and coefficients of the Taylor series expansions representing the farfield are kept constant during the interval.

The remaining nearfield interactions between an atom and the other atoms in the same cell and in neighboring cells are computed explicitly, using the appropriate charge-charge interaction equations (Coulomb or van der Waals).

Next / Previous / Table of Contents

Kian-Tat Lim