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

**
A. Fijany**^{1}, T. Cagin^{2}, A. Jaramillo-Botero^{2},
S. Gulati^{1} ,and W. A. Goddard III^{2}

^{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).
### Abstract

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.