Computational Methods in Markov Chains

该项目强调围绕离散马尔科夫链的平稳概率计算算法的应用和实施的实际和理论方面。特别关注使用离散模型来理解和分析由一组松散耦合的子系统组成的大系统的动力学的应用，例如在排队模型和网络、电信、计算机性能评估、随机自动机网络以及经济建模和预测的研究中。算法方面涉及基于聚集/分解技术的并行多水平方法的开发和分析-直接和迭代--并且这些技术中的一些被应用于涉及随机自动机网络的问题。体系结构方面涉及识别最适合实现马尔科夫链算法的矢量和并行计算机的功能。理论部分包括研究马尔可夫链的性质。然后，这些思想被用来产生误差分析，目的是了解多级聚集/解聚算法的收敛和稳定性特性。

This project emphasizes practical as well as theoretical aspects surrounding the application and implementation of algorithms for computing stationary probabilities of discrete Markov chains. Special attention is devoted to applications in which discrete models are used to understand and analyze the dynamics of large systems comprised of a collection of loosely coupled subsystems such as in the study of queuing models and networks, telecommunications, computer performance evaluation, stochastic automata networks, and economic modeling and forecasting. Algorithmic facets concern the development and analysis of parallel multilevel methods based on aggregation/disaggregation techniques---both direct and iterative--- and some of these techniques are applied to problems involving stochastic automata networks. An architectural aspect involves the identification of features of vector and parallel computers that are best suited for implementing Markov chain algorithms. Theoretical components involve studying properties of Markov chains. These ideas are then used to generate error analyses aimed at understanding the convergence and stability properties of multilevel aggregation/disaggregation algorithms.