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.
