Mathematics of Simulations
Sequential dynamical systems (SDS), which came out of the research done in FOSS allows us to analyze the generic features of simulations. The main features and constituents of simulations are:
Entities/Objects/Actors
Examples of entities in a simulation are, e.g., a car in a traffic simulation, a molecule in gas dynamics simulations, a station in an IP network simulation and so on. An entity usually has a state reflecting its properties.
Communication links
Entities communicate or exchange full or partial information about their states. Typically, entities only communicate with nearby entities.
Update rules
Each entity has a rule or a set of rules for they update their state. An entity replacing its old state with the state computed by its local function is referred to as an update of that entity.
Update mechanism
A computer simulation has a rule or mechanism that schedules the individual updates of entities. Some common choices include sequential updating, parallel updating, random updating and event-driven updating.
Typically, we will have perfect knowledge about each object in isolation. The complex dynamics of the simulation results from composition of local rules. The goal of SDS research is to obtain information about the global dynamics of a simulation based on the local information we have, and without implementing and running the actual computer simulation.
Sequential Dynamical Systems
Our research is centered around an abstraction of the above description of a computer simulation. The objects in an SDS are the vertices of some graph Y, and each of them has associated a binary state. The edges of the graph Y represents the communication links among objects. For each object there is a (symmetric) local function. The objects are update sequentially according to a fixed schedule or permutation.
SDS capture essential features of simulations such as scheduling and dependencies. They allow us to study e.g. equivalence of schedules in an abstract setting, and thus addressing the question of, e.g. validity. The nature of the work on SDS falls into the categories of algebra, combinatorics, dynamical systems and probability theory.
Some topics and questions we have studied include:
- Defining "inequivalence" of dynamical systems and determine the number of inequivalent dynamical systems that can be obtained through rescheduling.
- Investigate the effects of symmetries of the Y-graph on the corresponding phase portraits/phase spaces of SDS.
- Designing a "relative" theory in the sense of analyzing how changes in the Y-graph affect the underlying dynamical system. Effects of stochasticity in one or more of the constituents of an SDS. Dynamical system issues such as fixed points and structure of periodic orbits.
|
