Mathematical Algorithms for Computer Simulation

计算机模拟的数学算法

• 批准号: 0511441
• 负责人: Reinhard Laubenbacher
• 金额: $ 15万
• 依托单位: Virginia Polytechnic Institute and State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-09-15 至 2008-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0511441&HistoricalAwards=false
• 关键词: Mathematical; Algorithms; 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.

该项目专注于为基于交互的计算机模拟开发一个数学基础，该模拟可以表示为有限状态集上的确定性、离散时间动态系统。这里，基于交互的模拟被认为是变量的集合，每个变量都配备了一个更新函数或一组规则，用于基于所有其他变量的状态来计算该变量在下一个时间步长的状态。因此，通过局部相互作用给出系统的描述，通过所有局部更新函数的同时迭代产生全局动态。元胞自动机和布尔网络就是这样的模拟。一个在元胞自动机框架内被广泛研究的重要问题是如何根据局部更新函数的结构来预测这类系统的全局动力学特征。通过假设每个变量的状态集是一个有限域，例如通常用于元胞自动机的具有两个元素的域，这个问题可以在计算代数的框架内得到解决。在这个项目中开发的算法将成为有限动力系统符号计算软件包的一部分，该软件包在计算机代数系统Macaulay2中实现。基于交互作用的模拟在分析大型生物、流行病学和社会技术网络，如免疫系统、传染病在城市地区的传播，或道路交通和无线通信网络方面正变得越来越重要。通常，这样的网络是在个人互动的层面上被理解的，但全球信息往往是稀疏的。由于仿真系统的规模和复杂性，这类系统的软件设计和仿真输出的分析都是非常具有挑战性的。这类模拟的数学基础将为设计大规模模拟提供工具。它还将有助于系统地回答有关生物和其他系统的问题，例如治疗传染病的最佳方法，或如何控制其在大量人口中的传播。