Cell Multipole Method
The cell multipole method is available in the Discover 95.0
program only.
Contents
The cell multipole method (CMM) provides a treatment of the nonbond
interactions for nonperiodic systems that is more rigorous and
efficient than the application of cutoffs. This recently developed
method (Greengard and Rokhlin
1987, Schmidt and Lee
1991, Ding et al. 1992) is a
hierarchical approach that allows the accuracy of the nonbond
calculation to be controllable. It scales as N.
The cell multipole method applies to the general energy expression of
the following form:
- Eq. 2-7:
-
where 
i is the potential
at atom i, Rij is the distance between
atom i and atom j, p is a number (p = 1
for Coulombic and 6 for London dispersion interactions, for example),
and the 
's are general charges. For
Coulombic interactions, the 's are real
charges.
The general potential i
may be divided into a near-field potential due to the surrounding
atoms (those within a few angstroms) and a far-field potential due to
the rest of the atoms that interact with the ith atom.
The number of interactions in the near field is limited, so it is
relatively easy to calculate the near-field potential exactly. The
number of interactions in the far field is of order
N 2, making an exact calculation of this potential
intractable for large molecules. The cell multipole method calculates
the far-field potential accurately and efficiently as described under
Implementation of the CMM Method.
We begin by placing an arbitrarily shaped molecule in a rectangular
box. The box is then cubed into a number of basic cells of length 4-6
Å and containing 2-4 atoms on average. The basic cell level is
denoted level A in Figure
2-9. Starting from a corner of the box, every eight basic cells
may be considered to constitute a larger, parent cell, termed
level B. Every eight parent cells may constitute a
grandparent cell, termed level C. This procedure is
repeated until only a few large cells fill the box. For example,
considering any atom in cell A0 of the three-level
cell system (Figure 2-9) the
other atoms in A0 and all atoms in
An contribute to the near-field potential,
and the atoms in Af, B, and C
contribute to the far-field potential.
The cell multipole method involves the following two key steps:
- Multipole expansion and calculation of general multipole moments
The potential associated with each basic cell can be represented as a
general potential originating at the center of the cell. This
potential may be expanded into an infinite series of multipole
moments. For example, the potential associated with cell
Af in Figure 2-9 centered at
rAf, is expressed as:
- Eq. 2-8:
-
where R = rAf - r; r is
any point outside cell Af; 
, 
= x, y, z; and
Z, D, and Q are monopoles, dipoles, and
quadrupoles, respectively.
The potentials associated with the higher-level cells can be expanded
in an analogous manner, with moments derived from lower-level cell
moments.
- Generation of Taylor coefficients
Using this expansion to represent the potentials associated with
Af-, B-, and C-level cells, the
far-field potential of cell A0 may be obtained by
summing all the far-cell contributions. The resulting potential may
now be expanded as a Taylor series about the center of cell
A0:
- Eq. 2-9:
-
where rA0 is the position vector
of the center of cell A0 and 
r
=
r -
rA0. The Taylor coefficients in Eq. 2-9 are due to all the far-cell
contributions.
A key point of the cell multipole method is that, once the set of
Taylor coefficients is calculated at
rA0, the far-field potential of
any atom in cell A0 is obtained easily through Eq. 2-9.
Since the Taylor coefficients must be generated for every basic cell,
another key point of the cell multipole method is efficient generation
of these coefficients. A hierarchical procedure is used, in which
coefficients determined for higher-level cells are propagated to the
coefficients for lower-level cells. Thus, coefficients for a child
B cell are obtained by adding contributions directly translated
from the C-level coefficients at the center of the parent
C cell to the coefficients at the center of B, generated
by considering only the B-cell contributions.
The cell multipole method is an order N method as discussed
elsewhere (Greengard and
Rokhlin 1987, Schmidt and Lee
1991, Ding et al. 1992). The
time savings with respect to an exact N 2 algorithm,
as well as the improved accuracy relative to using cutoffs, can be
dramatic. Table 2-1 shows
results from several calculations on hemoglobin. When the conventional
method with 9.5-Å cutoffs is used, the computational and setup
times are greatly reduced, but at the cost of a disturbingly large
error (over 1% of the correct energies). The last 6 lines of the table
show results for second-, third-, and fourth-order multipole
expansions at two levels of computational accuracy. The short-range
treatment becomes progressively better towards the bottom of the
table. However, the overall CPU time required increases. It is
practical to achieve essentially exact results (within a fraction of a
kcal mol-1 ) in reasonable times.
For larger systems than hemoglobin, the improvement in performance can
be even more dramatic. For a system ten times larger, the cell
multipole method would take 3-10 minutes for the energy evaluation,
depending on the accuracy desired. The exact N 2
calculation, in contrast, would take about three days!
Main
access page 
Theory/Methodology access.
Describe-System access
Nonbond Cutoffs
Ewald Sums
Copyright Biosym/MSI
