next up previous
Next: Combination of SAMM with Up: The FAMUSAMM algorithm Previous: Structure Adapted Multipole Method

Multiple Time Step Methods


Another class of approximation schemes, the multiple-time-step methods [28, 29, 32, 16, 33] , exploit complementary properties of protein electrostatics for the same purpose; they take advantage of temporal regularities. The so-called distance class methods, in particular, are based on the observation that forces originating from distant atoms fluctuate more slowly than forces from atoms nearby (see Figure 3). The slowly fluctuating forces may be evaluated less frequently than the fast ones and may be extrapolated at the time steps in between. Such extrapolation is required as the numerical integration of the dynamical equations needs all forces at every integration time step tex2html_wrap_inline1227, which discretizes the simulation time tex2html_wrap_inline1229, where tex2html_wrap_inline1231 is the integration time step sizegif.

Figure: (left) Distance classes j=0,1,2,.., are defined for an atom (central dot) by a set of radii tex2html_wrap_inline1235 generating a series of spherical shells; (right) also shown is for each distance class the temporal evolution of the total force tex2html_wrap_inline1237 acting on the selected atom originating from all atoms in the respective distance class; along with the exact forces (solid line) and their exact values (filled squares) also linear force extrapolations (dotted lines) and resulting force estimates (empty squares) are depicted.

The left part of Figure 3 illustrates how distance classes j can be defined by a set of increasing radii tex2html_wrap_inline1235. The set of atoms tex2html_wrap_inline1243 at positions tex2html_wrap_inline1245 satisfying tex2html_wrap_inline1247 makes up the distance class j of particle l at position tex2html_wrap_inline1253. As is also indicated in Figure 3 (right part), for each particle l the sum of forces tex2html_wrap_inline1237 arising from particles in distance class j is calculated explicitly every tex2html_wrap_inline1261-th integration time step (filled squares). Each of these time steps is called a macro integration step. A common choice [16] is tex2html_wrap_inline1263. Correspondingly, the tex2html_wrap_inline1265 elementary time steps within the cycle of a macro integration step are called micro integration steps. As sketched in Figure 3, at each step tex2html_wrap_inline1237 is estimated from two forces calculated at previous macro integration steps by
using appropriate extrapolation coefficients tex2html_wrap_inline1269 and tex2html_wrap_inline1271. The lower index of tex2html_wrap_inline1273 denotes the absolute integration time step number and is expressed in terms of the macro integration step tex2html_wrap_inline1275 and the cyclic micro integration step tex2html_wrap_inline1277; tex2html_wrap_inline1279 and tex2html_wrap_inline1281 are explicitly calculated at the macro integration steps k and k-1.

The hierarchical extrapolation procedure sketched above is capable to save an enormous amount of computer time as it frequently avoids the most time consuming step, i.e., the exact evaluation of all interactions. Here computational speed is gained at the cost of an increased demand for memory: for each atom and each distance class two previous forces have to be kept in memory.

Various choices for the extrapolation coefficients tex2html_wrap_inline1287 and tex2html_wrap_inline1289 have been discussed [16, 33, 37]; both the linear extrapolation (illustrated in Figure 3) and the so-called DC-1d algorithm have been found promising [16]. Although the linear extrapolation defined by
entails smaller discontinuities for the extrapolated forces than the DC-1d algorithm, it leads to a larger energy transfer into a simulation system by algorithmic noise [16]. The DC-1d scheme employs the coefficients

It is a priori not clear, whether the quoted properties of these extrapolation schemes will pertain, if they are combined with the SAMM procedure into our new FAMUSAMM scheme, which will be explained in the next section. Therefore, using test simulations we will subsequently check both extrapolation methods for their suitability within our combination method.

next up previous
Next: Combination of SAMM with Up: The FAMUSAMM algorithm Previous: Structure Adapted Multipole Method

Helmut Grubmueller
Wed Apr 30 15:40:09 MET DST 1997