Novel Algorithms for Massively Parallel, Long-Term, Simulation of Molecular Dynamics Systems

A. Fijany1, T. Cagin2, A. Jaramillo-Botero2, S. Gulati1 ,and W. A. Goddard III2

1 Jet Propulsion Laboratory, California Institute of Technology
2 Material and Process Simulation Center, Beckman Institute, California Institute of Technology

Advances in Engineering Software 29, 441-450 (1998).


In this paper a novel algorithm for solution of constrained equations of motion with application to simulation of molecular dynamics systems is presented. The algorithm enables the solution of equation of motion with an internal coordinates model wherein the high frequency oscillations are freezed by explicit inclusion of hard constraints in the system as well as by clustering of atoms and thus it allows a much larger time step in the integration. For a molecular system with N clusters, the algorithm achieves the optimal sequential complexity of O(N). However, the main advantage of this new algorithm is its efficiency for massively parallel computation. In fact, this is the first known algorithm that achieves a both time- and processor-optimal parallel solution of constrained equations of motion, i.e.,a computation time of O(Log N) by using O(N) processors. In addition to its theoretical significance, this algorithm is also very efficient for practical implementation on coarse grain, MIMD, parallel architectures due to its highly decoupled computational structure.