The Numerical Treatment of Markov Chains

本计画将探讨离散型之数值解 马尔可夫链，重点是稳态的计算 遍历链的向量 虽然这个问题可以被看作是一个 一般的特征值问题，它在两个方面是特殊的。 一是 所讨论的本征值（即1）是确切已知的。 第二，许多 排队模型等应用具有特殊的结构 可以通过计算加以利用。 因此，不同的方法 其中，有一些是不为人知的。 的目标 这项工作是为了提高他们的理论，他们的理解， 相互关系及其实施，特别是平行的 实现，从方法的分类开始， 然后专注于特别有前途的算法。

This project will investigate the numerical solution of discrete Markov chains, with an emphasis on the computation of the steady-state vector of ergodic chains. Although the problem can be cast as an ordinary eigenvalue problem, it is special in two ways. First, the eigenvalue in question, namely one, is known exactly. Second, many of the applications, such as queuing modeling, have special structure that can be exploited computationally. Consequently, diverse methods have been set forth, some of which are poorly understood. The goal of this work is to improve understanding of their theory, their interrelations, and their implementation, particularly parallel implementations, beginning with a classification of the methods and then focusing on particularly promising algorithms.