An algorithm for the simulation of condensed matter which grows as the 3/2 power of the number of particles

Abstract

Current supercomputers and the impending availability of large scale parallel machines makes possible the study by molecular dynamics of a number of fundamental problems in condensed matter science hitherto beyond our scope because of the enormous computing time involved. This is because a realistic model of such systems contains one or two orders of magnitude more particles than the systems studied to date. Moreover, the intermolecular forces between these particles will usually include contributions from distributions of permanent electric charges, so that the usual assumption of short-ranged forces cannot be made. We give a list of typical problems in this class and attack the problem of improving the performance of molecular dynamics algorithms to take advantage of these new architectures. We use the Jacobi theta function transformation to derive rapidly computable forms for the energy of and forces between large assemblies of N particles interacting in periodic boundary conditions as the sum of real space pair-pair interactions and one particle sums in reciprocal Fourier space. By suitable choice of the separation constant controlling the relative overheads of the two contributions, we show that the total overhead grows as N ^3/2. We present an experimental investigation of the N dependence of the computing overhead performed on a Siemens VP200 vector processor. The advantages of the algorithm for parallel computation are also discussed.