Novel algorithms for massively parallel, long-term, simulation of molecular dynamics systems

In this paper, a novel algorithm for solution of the constrained equations of motion with application to simulation of the molecular dynamics systems is presented. The algorithm enables the solution of equations of motion with an internal coordinates model wherein the high-frequency oscillations are frozen by explicit inclusion of hard constraints in the system as well as by clustering of atoms and, thus, allowing 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 for the constrained equations of motion, i.e. an optimal computation time of O(logN) by using an optimal number of O(N) processors. In addition to its theoretical significance, this algorithm is also very efficient for practical implementation on the coarse grain MIMD parallel architectures owing to its highly decoupled computational structure.