Algorithms for Complex Systems

Colorado State University, Fort Collins CO

Investigators

Abstract

Complex systems arise in many scientific problems. They are high dimensional structures, comprised of many locally interacting agents, with emergent phenomena often occurring at multiple length and time scales. Such systems have global structural and dynamical properties that are usually impossible to determine exactly. Instead, these properties must be estimated by computer experiment and simulation. Unfortunately, due to the size and multiscale effects in complex systems, straightforward algorithms are often too slow. Thus, fast algorithm design, along with a rigorous study of accuracy, is crucial. This research project focuses on designing, improving, and quantifying the error of state-of-the-art algorithms for complex systems. Potential applications include a wide range of problems arising in materials science, computational chemistry, and solid-state physics. In particular, the methods studied could help pave the way for cheap and efficient in silico drug design. The principal investigator will analyze state-of-the-art algorithms using a mixture of rigorous mathematical analysis and computer experiment. An important application will be the efficient simulation of metastable systems, in which the system dynamics tend to remain for very long times in certain subsets of state space. Such systems are widespread in molecular dynamics, an increasingly important tool in computational chemistry. In molecular dynamics, metastability arises from the well-known time scale problem: atomic vibrations occur on a time scale much smaller than that of thermally activated reactions and other interesting dynamical events. For this reason, it is usually impossible to observe the most interesting aspects of the dynamics by direct atomistic simulations. For metastable dynamics, many approximate simulation methods serve as alternatives to direct atomistic simulation, but they are limited by applicability and accuracy. The project will focus on several methods for overcoming metastability, including the parallel replica method, milestoning, and kinetic Monte Carlo. The PI will introduce a mathematical framework for generalizing these algorithms, based largely on the quasi-stationary distribution, a mathematical object that encodes metastability. The PI will show how the more general framework leads to new applications, including more efficient simulation of Markov State Models and glasses. Moreover, the PI will use this framework to pursue rigorous error estimates, which are crucial for extracting quantitative information from simulations.