A Parallel Implementation of the GTH Algorithm

The Grassmann–Taksar–Heyman algorithm is a direct algorithm for computing the steady-state distribution of an finite irreducible Markov chain. We describe our experience in implementing this algorithm on a single-instruction multiple-data parallel processor computer. Our main conclusions are that a lower-level language has a performance advantage compared to Fortran, and that data storage is the limiting factor that determines the largest problem that can be solved. As a consequence, we devote considerable attention to storing a block tridiagonal transition matrix.