Multi-Scale Methods in Time and Space for Particle Simulations.

Particle simulations arise in many applications such as gravitational N-body problems, electrostatics, and molecular dynamics simulations. The motion of the particles is governed by Newton's equations of motion. Since the system of equations is typically non-linear, its solution requires numerical simulation via time integration. During each integration step the force on each particle needs to be computed. If long-range forces such as gravity or electrostatics are present the direct evaluation of the force for an N-particle system is an O( N2) procedure which quickly becomes intractable for large systems. Two common approaches for improving the computational efficiency of the force evaluation, and hence particle simulations, are computing the force less frequently and computing the force more efficiently. In this dissertation we discuss how multi-scale methods in time and space can be applied towards this end. One way to compute the force less often is to assign a larger time step to the long-range forces. While the idea of multiple-time-stepping (MTS) has been explored in previous works, we will formulate a class of integrators called asynchronous variational integrators (AVI) in the context of particle simulations that allows for time steps to be chosen in arbitrary ratio. Although MTS schemes can be used to reduce the cost of particle simulations, there are potential drawbacks such as the presence of instabilities whose manifestation is dependent on the choice of time steps. A thorough linear stability analysis of AVI is performed to explore this issue. AVI is also extended to accommodate Langevin dynamics which is commonly used as a stochastic thermostat for molecular dynamics simulations of proteins. While using multiple time steps reduces the cost of force evaluations, this reduction is only by a constant factor i.e. the scaling is still O(N2) for long-range forces. One method that improves the scaling to O(N) is the fast multipole method (FMM). The FMM is a tree-based method that uses analytical formulae to construct a low-rank approximation for far-field interactions. Since the low-rank approximation is dependent on the functional form of the interaction, a new FMM would need to be derived and implemented for other types of long-range interactions. Therefore it would be convenient to have a black-box method that is applicable to a wide class of interactions. The construction of a black-box FMM and its extension to periodic systems are described in detail. In addition to computational efficiency, improvements can also be made by introducing novel techniques that enable the use of particle simulations in a new application area. We conclude by discussing how conventional periodic boundary conditions can be extended to handle torsion and bending and illustrate this by applying it to molecular dynamics simulations of silicon nanowires.