A fast algorithm for massively parallel, long-term, simulation of complex molecular dynamics systems

In this paper a new algorithm for solution of constrained equations of motion (EOM) with application to simulation of molecular dynamics systems is presented. The algorithm enables the solution of EOM 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 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 EOM, 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 parallel architectures due to its highly decoupled computational structure.