AN ADAPTIVE MULTIGRID TECHNIQUE FOR EVALUATING
LONG-RANGE FORCES IN BIOMOLECULAR SIMULATIONS

Leonid Y. Zaslavsky and Tamar Schlick

Courant Institute of Mathematical Sciences
and Chemistry Department, New York University
Howard Hughes Medical Institute
251 Mercer Street, New York, NY 10012


Abstract

Multiresolution is an important principle in computational modeling of biomolecular systems where many scales of temporal and spatial resolution are relevant. Since physicists are interested in capturing long-time ``essential'' dynamics, in addition to small timescale fluctuations, different approximation schemes can be applied on disparate scales to make possible dynamical simulations of biologically important events.

We propose an adaptive multigrid method for evaluating the non-local, long-range interactions in modeling biomolecular systems. Our method provides O(h³) accuracy, where h is the mesh size of the finest cubic grid, compatible with highly approximate nature of the molecular force fields used to simulate biomolecules. The method can be applied to both Newtonian and Langevin dynamics simulations.

Approaches for fast summation are based on different kinds of hierarchical approximations, like fast multipole and multigrid methods, or Fast Fourier Transforms, like the Ewald method. Our technique is developed in the multigrid framework. Two new algorithmic components are included: an adaptive technique for spreading a three-dimensional charge distribution to a space mesh, and a procedure for performing coarse-to-fine grid interpolation of the potential, force components, and their derivatives (grid-to-particle interpolation at the finest level) in a consistent fashion.

The adaptive mesh used in the spreading procedure contains two types of nodes: regular, positioned at nodes cubic grid, and flexible, one per cubic cell. Thus, the charges located in each grid cell are spread to these nine nodes. The method conserves charge, dipole, and quadrupole moments of cells.

Our interpolation procedure allows us to consistently interpolate the potential, force components, and their first spatial derivatives from eight nodes surrounding a rectangular cell to a point inside this cell. In such a way, the method achieves third-order accuracy overall for forces even though the stencil size is minimal.

The spreading and interpolation techniques are economical in computation time and storage due to the overlap design in the stencils. The low computational cost, combined with a suitable level of accuracy, makes the method attractive for fast summation procedures of the electrostatic potential and forces in dynamic simulations of biomolecular systems.