Robert Skeel of Purdue University and Klaus Schulten from University of Illinois Urbana-Champain have received a collaborative award from the Theory, Models and Computational Methods. The project focuses on the creation, analysis, and implementation of methods of broad applicability for calculating pairwise interatomic interactions in atomistic computer simulations with applications in chemistry, physics, and materials science.
Atomistic simulations of macromolecules, biomolecules, nano-systems, and condensed phases of atomic or molecular systems require vast amounts of computer time. Typically, the bulk of this time is spent on calculating pairwise interactions between particles. The calculation of pairwise interactions is done either directly or with standard tools like the fast multipole method or the particle-mesh Ewald sums. This proposal will investigate the advantages of a less well known O(N) algorithm, the multilevel summation method (MSM). This algorithm has the potential of becoming very useful for approaches such as molecular dynamics. The project will explore creative implementations involving mathematical techniques for improving the software and exploring implementation in emerging hardware like GPUs. It is the objective of the proposal to study the efficiency and scalability of MSM as applied to several interdisciplinary molecular dynamics problems, to analyze the implication of approximations both theoretically and experimentally, and to implement and disseminate the results.
The project provides an opportunity for graduate students to engage in high-impact interdisciplinary research. Open source implementations of the algorithms as libraries of modules will be made available. The software modules will also be embedded in simulation software such as NAMD. Molecular dynamics has applications beyond chemistry, and N-body solvers have applications outside of molecular dynamics. Better methods and software in the hands of scientists will enable chemical and biomolecular simulations of much larger systems with improved accuracy, and this will result in benefits to society. The impact will be broad.
The goal of the project has been to construct a faster algorithm for the calculation of energies and forces among a large set of particles. The typical scenario is that of electrostatic forces acting on atoms or larger particles; another is that of gravitational forces acting on galaxies of stars. Such calculations are used in chemistry, materials science, biology, and mechanical engineering, as well as physics.They are performed both for understanding and for the design of new molecules and materials.Typically, a single simulation does such a calculation millions of times,either for investigating myriads of possibilities or for doing dynamical simulations to see how a system evolves in time. A simple algorithm for doing the calculation based on physics formulas requires a number of arithmetic operations proportional to the square of the number of particles. Fast algorithms can do this with a number of operations proportional to the number of particles (or nearly so).They do this by means of complicated approximations having controllable error.The algorithm developed here is an improvement of a technique called multilevel summation, which the investigators believe possesses almost every advantage of the alternative techniques. The study here has replaced the approximation method of multilevel summation with B-splines, a popular method for curve-fitting and design. B-splines have superior approximation properties but their application is not straightforward. These difficulities have been overcome and B-splines have been implemented in a software prototype. Mathematical analysis and numerical experiments indicate an order of magnitude reduction in error, which should translate into a substantial reduction in the number of arithmetic operationsto attain acceptable accuracy. Preliminary work has been published, and final results are being prepared for dissemination in a journal article and in software. The project employed, as a research assistant, a U.S. graduate student, who is a first in his generation to attend college. The work providedtraining and laid groundwork for a Ph.D. thesis.
