A parallel implementation of the Grassman–Taksar–Heyman algorithm

The Grassman–Taksar–Heyman algorithm is a direct algorithm for computing the steady-state distribution of a 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.