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

We propose an adaptive multigrid method for evaluating the nonlocal, l ong-range interactions in biomolecular models. The method provides O(h (3)) accuracy for the forces, where h is the mesh size of the finest c ubic grid, even though the stencil size is minimal. Two new algorithmi c components are developed: an adaptive technique for spreading a thre e-dimensional charge distribution onto a space mesh, and a procedure f or performing coarse-to-fine grid interpolation of the potential, forc e 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, position ed at nodes cubic grid, and flexible, one per cubic cell. Thus, the ch arges located in each grid cell are spread to these nine nodes. The me thod conserves charge, dipole, and quadrupole moments of cells. The sp reading and interpolation techniques are economical in computation tim e and storage due to the overlap design in the stencils. Implementatio n is also straightforward. Our initial tests demonstrate the favorable performance for low accuracy with respect to the fast multipole techn ique. (C) 1998 Elsevier Science Inc. All rights reserved.