Mathematical Algorithms for Computer Simulation

点击翻译按钮获取中文摘要

The project focuses on the development of a mathematical foundationfor interaction-based computer simulations that can be represented as deterministic, discrete-time dynamical systems onfinite state sets. Here, an interaction-based simulation isconsidered to be a collection of variables, each equipped with an update function or a set of rules which is used to compute the stateof that variable at the next time step, based on the states of allthe other variables. Thus, the description of the system is givenvia local interactions, and global dynamics is generated throughthe simultaneous iteration of all local update functions. Cellular automataand Boolean networks are examples such simulations. An importantquestion, that has been studied extensively in the framework ofcellular automata is how one can predict global dynamical features ofsuch systems from the structure of the local update functions. By assuming that the state set for each variable is a finite field,such as the field with two elements used typically for cellularautomata,this problem can be addressed within the framework of computationalalgebra. The algorithms developed in this project will become part ofa symbolic computation software package for finite dynamical systems,implemented in the computer algebra system Macaulay2. Interaction-based simulation is becoming increasingly important in theanalysis of large biological, epidemiological, and socio-technical networks, such as the immune system, the spread of infectious diseasesin urban areas, or road traffic and wireless communications networks. Typically, such networks are understood at the level of individualinteractions, but global information tends to be sparse. The softwaredesign of such systems is very challenging, and so is theanalysis of simulation output, due to the size and complexity of thesimulated systems. A mathematical foundation for such simulationswill provide tools for the design of large-scale simulations. Itwill also help to systematically answer questions aboutbiological and other systems, such as optimal ways to treat infectious diseases,or how to contain their spread in large populations.