Computational Methods in Markov Chains

这项研究涉及在现代多处理机计算机上计算大规模马尔可夫链的平稳概率的算法的发展和分析。大规模问题的平稳概率的计算是诸如计算机建模、计算机性能评估、排队网络之类的各种应用中的基本关注点，并且更一般地，在使用离散数学模型来理解由松散耦合的子系统的集合组成的超大型系统的动力学的应用中。将强调在各种多处理器计算机上的并行和向量实现，正在研究的具体技术包括子空间迭代方法；混合迭代-直接算法；重叠块迭代方案；并行聚集和迭代方法；以及块消除算法。这项工作的架构方面涉及确定最适合实施这些技术的当代矢量和并行计算机的那些功能，在这方面，将继续使用各种机器，包括Alliant FX/系列、Sequent Balance和Cray Y-MP。

The research concerns the development and analysis of algorithms for computing the stationary probabilities of large scale Markov chains on modern multiprocessor computers. The computation of stationary probabilities for large scale problems is a fundamental concern in a wide variety of applications such as computer modeling, computer performance evaluation, queueing networks, and more generally, in applications where discrete mathematical models are used to understand the dynamics of very large systems comprised of a collection of loosely coupled subsystems. Parallel and vector implementations on a variety of multiprocessor computers will be emphasized and specific techniques under investigation include subspace iteration methods; hybrid iterative-direct algorithms; overlapping block iterative schemes; parallel aggregation and iteration methods; and block elimination algorithms. The architectural aspect of the work involves the identification of those features of contemporary vector and parallel computers which are best suited for implementing these techniques, and in this regard, a variety of machines, including the Alliant FX/series, the Sequent Balance, and the CRAY Y-MP will continue to be used.