Interdisciplinary Applied Mathematics

Скачать в pdf «Interdisciplinary Applied Mathematics»

from potential truncation and neighbor list strategies (Sadus, 1999). The philosophy behind these computational strategies is to identify and distinguish between neighboring molecules that make only small contributions. This distinction between near and far interactions can be handled efficiently by ordering the molecules in a hierarchical tree structure. The tree-based methods provide large gains in computational efficiency, particularly for calculation of long-range interactions. For example, the fast multipole method (FMM) is of order N compared with N2 (or N3/2) for a traditional particle-particle calculation.

The fast multipole method was developed using the hierarchical tree concept (Greengard, 1987; Greengard and Rokhlin, 1987; Carrier et al., 1988; Schmidt and Lee, 1991). The FMM algorithm involves multipole expansion    for    boxes    at    the    lowest    level    of    the    tree.    These

expansions are combined and shifted as they are passed up and down the tree. Particles are assigned to the cells at the finest level of the tree. In    the    FMM    algorithm    some    cells    may    be empty,    while    some

cells may have several particles. The multipole expansion of the particle configuration on the finest level is formed about the center of the box. Each “child” box communicates this information to the “parent” box on the next level. Aggregate information about distant particles comes back down the low-level boxes. In the FMM algorithm, the simulation box    of    length    L is    subdivided    into    a box    of    length    L/2r,

where r is an integer representing the level of refinement. The division is equivalent to forming 8r equal-sized subvolumes. This is done for every single box to a maximum level of refinement R irrespective of the number of particles that they contain. The maximum level of refinement R is approximately equal to the number of particles (N), i.e., R = log8 N. At the maximum level there is on average one particle per box.

Скачать в pdf «Interdisciplinary Applied Mathematics»