From:	Helmut Grubmueller <H.Grubmueller -AatT- Physik.TU-Muenchen.DE>
Date:	Tue, 13 Oct 92 9:47:05 MET
Subject:	On the use of Cut-off Schemes in MD

Dear Netters,

Arne Elofsson writes:
> Let's assume that there is something really strange about
> these simulations. What can we then do about it ? I have
> a suggestion that involves a collaboration all over the world.
> If every one spend some computing time on the same system,
> i.e. the same peptide but different forcefileds, box sizes ..
> Would we not be able to together solve this problem that is
> important to all of ous. For practical reasons maybe it is
> easier to limitate this kind of study to a few labs (five to ten).
> If there is an interest in this kind of study I would
> consider spending some time organize contacts. I think this
> list is the best forum to discuss what should be studied and how.


I strongly support the idea of a large-scale empirical
check of the effects of the cut-off method.
One has to careful, however, not to mix up physics/chemistry and
numerics:

It is one problem to find a *physical model* of a molecular
system that approximates reality.

It is another problem to find *numerical* algorithms/approximations
to speed up simulations employing that model.

Both problems are nearly independent and should therefore be discussed
independently. The cut-off method was introduced to save computer time,
and should therefore be regarded as an approach to the second, *numerical*
problem. Note that this does not mean, that a cut-off-simulation is generally
less accurate (as compared to reality) than one involving all Coulomb
pair interactions. In many situations the opposite is actually the case
(this is considered to be due to an imitation of shielding effects
by the cut-off method).
Consequently, the following remarks are meant to clarify the *numerical*
aspects arising from the long-range character of the Coulomb interaction.

1) Many people working in this field seem to think that the only way
   to save computer time in doing MD-simulations in volvong long-range
   interactions is to employ one of
   the well known cut-off schemes available in most MD-packages.
   This is, however, not the state of the art.
   In recent years, a whole bunch of methods have been developed
   to speed up the simulations of multi-body systems considerably
   *without* any significant loss (i.e. significant in the course
   of MD-simulations) of accuracy. Generally speaking, these methods
   replace the tradeoff between efficiency and accuracy by a tradeoff
   between *memory requirement* and accuracy,
   which turned out to be a serious obstacle in former times. With the
   availability of very cheap memory chips, however, this limitation is
   vanishing.
   Two methods may suffice to exemplify this statement:
   a) The fast multipole method (FMM) by L. Greengard and V. Rokhlin
      is based on a sophisticated multipole expansion of the Coulomb
      potential. In contrast to the conventional method of summing up
      all pair interactions within the molecule, which requires of
      the order of (N^2)/2 operations (N being the number of charged
      atoms within the molecular system to be simulated),
      while the FMM is of order N. The constant of proportionality depends on
      the desired accuracy, which can be preselected.
      The FMM has already successfully been
      employed for MD-simulations. As could be expected from this
      scaling behaviour, the FMM turns out to be most efficient for
      systems with large numbers of atoms,
      whereas it is comparably slow for small molecules. If I remember
      correctly, the break-even lies in the range of 1000...2000 atoms.
      To my very best knowledge, the FMM can only be applied for
      Coulomb-like potentials (i.e. 1/r). This may turn out to be a
      disadvantage, if one tries to include shielding effects caused
      by atomic polarizabilities.

      References hereto:

      L. Greengard and V. Rohklin:
      "A Fast Algorithm for Particle Simulations",
      J. Comp. Phys., pp.325-348, vol.73, 1987

      L. Greengard and V. Rokhlin:
      "On the Efficient Implementation of the Fast Multipole Algorithm",
      Research Report of the Yale University, Department of Computer Science,
      vol. RR-602, Feb., 1988

      L. Greengard and V. Rokhlin:
      "On the Evaluation of Electrostatic Interactions in Molecular Modeling",
      Chemica Scripta, 29A, pp. 139-144, 1989

      K. E. Schmidt and Michael A. Lee:
      "Implementing the Fast Multipole Method in Three Dimensions",
      J. Stat. Phys., submitted

      Edmund Bertschinger and James M. Gelb:
      "Cosmological N-Body Simulations",
      Computers in Physics, pp. 164-179, Mar./Apr., 1991

   b) Multiple time step (MTS) methods employing distance classes:
      This method, (which is not to be confused with *variable* time
      step methods), has also been successfully employed for MD-simulations
      (see refs below) and turns out to yield speed ups comparable
      to the FMM. The MTS method can be regarded as a generalization
      of the cut-off method in that intaractions of atom pairs separated
      by a large distance are not completely neglected (as it is the case
      for the cut-off method); instead, these interactions (forces) are
      computed less frequently and are approximated by extrapolation.
      Since, in contrast to the FMM, a rigorous error-analysis of the MTS
      seems to be impossible, I carried out large-scale test simulations
      on a model-protein. The results show, that the method achieves
      a considerably higher accuracy (as compared to simulations of the
      same protein employing a cut-off of 10 A), while beeing even more
      efficient. In addition, the method can be flexibly adjusted
      to specific molecular systems to allow an individual tuning
      of the tradeoff between efficiency, accuracy, and memory requirements.

      References hereto:

      S. J. Aarseth:
      "Direct Methods for N-Body Simulations" (chap.12), in
      "Multiple Time Scales", Academic Press, 1985, 1st edition.

      Helmut Grubmueller, Helmut Heller, Andreas Windemuth, and Klaus Schulten:
      "Generalized Verlet Algorithm for Efficient Molecular Dynamics
       Simulations with Long-Range Interactions",
      Molecular Simulation, Vol. 6, pp. 121-142, 1991

      Mark E. Tuckerman and Glenn J. Martyna and Bruce J. Berne:
      "Molecular dynamics algorithm for condensed systems with multiple
      time scales",
      J. Chem. Physics, vol. 93, #2, pp. 1287-1291, 1990

   It is worth noting that both methods described above have also been
   successfully implemented on parallel computers (MIMD) and a speed up
   increasing nearly linearly with the number of processors was achieved.
   Furthermore, it seems to be possible to combine both methods  in order to
   achieve even higher efficiencies.

2) The second point I want to make concerns the empirical
   comparison of different cut-off schemes by means of simulations carried
   out on identical molecular systems, as proposed by Arne Elofsson.
   As it turns out to be not at all a trivial matter, what quantities
   derived from the test-simulations should be compared in order to measure the
   numerical accuracy of the respective methods, I would like to make a few
   comments here:
   From a practical point of view, the results of an empirical test of the
   accuracy of different cut-off schemes should allow the estimation of
   the error of *relevant* physical quantities, that has to be expected when
   employing a particular scheme. Here, by *relevant* quantities, we mean
   observables, which are of central interest to the researcher carrying
   out a particular simulation. Since these depend entirely on the
   molecular system (model) under consideration, as well as on the questions
   the researcher wants to get answered, it is not possible to simply
   give a complete list of relevant quantities.
   It is, however, quite easy to give examples of quantities, which will most
   likely be *never* relevant in any MD-simulation, and which, given the quite
   obvious initial statement, should *not* be used to compare different
   cut-off schemes. One finds, however, that quite often just these
   irrelevant quantities are used as a criterion for the accuracy of
   some MD-algorithm under consideration.
   To be more specific, the test-quantities mostly encountered are atomic
   trajectories and conservation of total energy in a microcanonic simulation.
   Please note that I do *not* state that these quantities are not important.
   All I say is that these are not the quantities a biochemist is primarly
   interested in when performing MD-simulations.
   The problem that has to be solved is, therefore, to find a (possibly
   large) set of relevant quantities, which, in a sense, resemble
   typical situations encountered in the application of MD-simulations.
   Examples for quantities, that may be considered to belong to this
   set, and can thus be named 'relevant', are:

     * vibrational spectra
     * mean atomic positions and rms-fluctuations thereof
     * time autocorrelation functions of atomic positions/velocities
     * average values of different energy contributions (bond, Coulomb, etc.)
     * average values of radii of gyration
     * cross correlations of atomic motions
     * results of free energy computations
     * rates of conformational substate changes
     * configuration space densities (or densities in subspaces)
       (e.g. a histogram of the distance distribution between two atoms
	within the molecule)

   In my opinion, it could be useful for the project proposed by Arne,
   if one knew about what other quantities are considered relevant within
   the scientific community. I therefore ask you to help me to complete
   the above list by emailing me your
   suggestions (grubi &$at$& nirvana.t30.physik.tu-muenchen.de); I will post a
   summary. Please do not flood the mailing list with your suggestions.

      Helmut


==============================================================================

  Helmut Grubmueller

Technische Universitaet Muenchen
Theoretische Biophysik, Abt. T35                        Tel.: +49/89/3209-3767
James-Franck-Str. (ehem. Bauamt)                        Fax.: +49/89/3209-2444
W-8046 Garching
Germany                         email: grubi #*at*#
nirvana.t30.physik.tu-muenchen.de
==============================================================================


Similar Messages
06/07/1993:  Summary of hierarchical multipole methods
06/03/1993:  Hierarchical multipole solvers
04/04/1995:  Ewald sums
08/01/1996:  Re: CCL:M:Heat of formation calculation using MOPAC.
01/20/1997:  Summary:  Removing charges for an MD simulation
11/26/1997:  tRNA modelling: summary
03/11/1996:  Law of conservation of difficulty: violations.
10/14/1992:  Re: On the use of Cut-off Schemes in MD
04/28/1994:  Semi-empirical methods revisited
08/01/1995:  Spin contamination, effect on energy and structure.


Raw Message Text