macromolecular dynamics of proteins in which the components of x describe the positions in space of large numbers Numerical integration of Newton's equation in multiple dimensions plays an important role in many fields such as biochemistry of objects (e.g., stars or atoms). In particular, protein MD and astrophysics. Currently, some of the most important practical has applications in biochemistry, protein-folding, strucquestions in these areas cannot be addressed because the large ture-based drug design and biotechnology, and it is a major dimensionality of the variable space and complexity of the required application for parallel computers.
force evaluations precludes integration over sufficiently large time
The practical difficulty with MD simulations in these intervals. Improving the efficiency of algorithms for this purpose is therefore of great importance. Standard numerical integration problems is that computational cost restricts the time peschemes (e.g., leap-frog and Runge-Kutta) ignore the special strucriod that can be integrated with feasible computational ture of Newton's equation that, for conservative systems, constrains effort. The dominating cost comes from evaluating F; this the force to be the gradient of a scalar potential. We propose a has O(N 2 ) complexity even for the simplest potentials connew class of ''spatial interpolation'' (SI) integrators that exploit this taining only two-body terms and N is typically ศO(10 4 ).
property by interpolating the force in space rather than (as with standard methods) in time. Since the force is usually a smoother (In some, but not all, problems this can be reduced to function of space than of time, this can improve algorithmic effi-O(N log N) by using fast summation algorithms [1], but ciency and accuracy. In particular, an SI integrator solves the oneevaluation of F still dominates computational cost.) As a and two-dimensional harmonic oscillators exactly with one force result, the most important practical questions cannot be evaluation per step. A simple type of time-reversible SI algorithm addressed at the present time.
is described and tested. Significantly improved performance is achieved on one-and multi-dimensional benchmark prob-For example, the substrate-enclosing ''flaps'' of the hulems.