Computational Methods In Markov Chains

该项目的目标是研究围绕计算平稳概率和分析离散马尔可夫链的瞬态行为的算法的应用和实现的实践和理论方面。研究的一个方面是致力于应用离散模型来理解和分析由松散耦合子系统集合组成的大型系统的动力学，例如排队模型和网络、电信、计算机性能评估、随机自动机网络、经济和生物预测以及柔性制造系统的研究。特别关注使马尔可夫链技术广泛应用于不同领域的研究人员。具体的研究目标包括以下几个方面。(1)该项目旨在将特定马尔可夫链模型的属性与数值算法的特征联系起来，目的是设计一个筛子，从中可以提取出最适合给定应用的算法和实现。(2)另一个目标是发展理论和数值机制，以促进利用各种聚合/分解方法确定或估计大规模有限马尔可夫链的平稳概率。一个具体的目标是制定一个全面的误差理论，它可以简化和统一对广泛的聚合/分解过程和算法的分析。(3)该项目旨在开发可应用于随机自动机网络形式的马尔可夫模型的迭代算法的实用预处理技术。(4)最终目标是开发一个全面的软件包，为马尔可夫建模提供复杂的计算工具。目标是为应用领域的研究人员构建软件包，这些研究人员不想被技术数值分析细节所转移或沉浸其中。

The goal of this project is to study both practical and theoretical aspects surrounding the application and implementation of algorithms for computing stationary probabilities and analyzing transient behavior of discrete Markov chains. One facet of the research is dedicated to applications of discrete models for understanding and analyzing the dynamics of large systems comprised of collections of loosely coupled subsystems such as in the study of queuing models and networks, telecommunications, computer performance evaluation, stochastic automata networks, economic and biological forecasting, and flexible manufacturing systems. Special attention is devoted to making Markov chain technology widely available to researchers in diverse areas. Specific research objectives include the following aims. (1) The project seeks to relate properties of specific Markov chain models to characteristics of numerical algorithms with the goal of devising a sieve from which the most appropriate algorithm and implementation for a given application can be extracted. (2) Another objective is to develop both theoretical and numerical mechanisms to facilitate the determination or estimation of stationary probabilities of large-scale finite Markov chains by utilizing a variety of aggregation/disaggregation methods. A specific goal is to formulate a comprehensive theory of errors which can simplify and unify the analysis of a broad range of aggregation/disaggregation processes and algorithms. (3) The project seeks to develop practical preconditioning techniques for iterative algorithms which can be applied to Markov models which are formulated as stochastic automata networks. (4) A final objective is to develop a comprehensive software package which provides access to sophisticated computational tools for Markov modeling. The goal is to structure the package for researchers in applications areas who do not want to be diverted by or become immersed in technical numerical analysis details.