title: Inherent speedup limitations in multiple time step/particle mesh Ewald algorithms.
abstract: Multiple time step (MTS) algorithms present an effective integration approach to reduce the computational cost of dynamics simulations. By using force splitting to allow larger time steps for the more slowly varying force components, computational savings can be realized. The Particle-Mesh-Ewald (PME) method has been independently devised to provide an effective and efficient treatment of the long-range electrostatics interactions. Here we examine the performance of a combined MTS/PME algorithm previously developed for AMBER on a large polymerase beta/DNA complex containing 40,673 atoms. Our goal is to carefully combine the robust features of the Langevin/MTS (LN) methodology implemented in CHARMM-which uses position rather than velocity Verlet with stochasticity to make possible outer time steps of 150 fs-with the PME formulation. The developed MTS/PME integrator removes fast terms from the reciprocal-space Ewald component by using switch functions. We analyze the advantages and limitations of the resulting scheme by comparing performance to the single time step leapfrog Verlet integrator currently used in AMBER by evaluating different time-step protocols using three assessors for accuracy, speedup, and stability, all applied to long (i.e., nanosecond) simulations to ensure proper energy conservation. We also examine the performance of the algorithm on a parallel, distributed shared-memory computer (SGI Origin 2000 with 8 300-MHz R12000 processors). Good energy conservation and stability behavior can be demonstrated, for Newtonian protocols with outer time steps of up to 8 fs and Langevin protocols with outer time steps of up to 16 fs. Still, we emphasize the inherent limitations imposed by the incorporation of MTS methods into the PME formulation that may not be widely appreciated. Namely, the limiting factor on the largest outer time-step size, and hence speedup, is an intramolecular cancellation error inherent to PME. This error stems from the excluded-nonbonded correction term contained in the reciprocal-space component. This cancellation error varies in time and introduces artificial frequencies to the governing dynamics motion. Unfortunately, we find that this numerical PME error cannot be easily eliminated by refining the PME parameters (grid resolution and/or order of interpolating polynomial). We suggest that methods other than PME for fast electrostatics may allow users to reap the full advantages from MTS algorithms.
authors.affiliation: Department of Chemistry and Courant Institute of Mathematical Sciences, New York University and Howard Hughes Medical Institute, 251 Mercer Street, New York, New York 10012, USA.
authors.forename: Danny
authors.initials: D
authors.lastname: Barash
authors.forename: Linjing
authors.initials: L
authors.lastname: Yang
authors.forename: Xiaoliang
authors.initials: X
authors.lastname: Qian
authors.forename: Tamar
authors.initials: T
authors.lastname: Schlick
mesh_terms: D000465:Algorithms; D019295:Computational Biology; D003198:Computer Simulation; D019951:DNA Polymerase beta / Q000737:chemistry*; D008958:Models, Molecular; D008968:Molecular Conformation; D055672:Static Electricity
chemical_list: D019951:DNA Polymerase beta