A Parallel Implementation of the Block-GTH algorithm

Abstract

The GTH algorithm is a very accurate direct method for finding the stationary distribution of a finite-state, discrete time, irreducible Markov chain. O'Leary and Wu developed the block-GTH algorithm and successfully demonstrated the efficiency of the algorithm on vector pipeline machines and on workstations with cache memory. In this paper, we discuss the parallel implementation of the block-GTH algorithm and show effective performance on the CM-5.