A parallel block projection method of the Cimmino type for finite Markov chains

A parallel block projection method is used to approximate the stationary vector of a finite Markov chain. Block projection methods are very attractive for solving large chains thanks to their potential for parallel computation and robustness. We show that the block Cimmino method is particularly well-suited if the chain is nearly uncoupled, a condition which is often met in the applications. This is due to the favorable spectral distribution of the iteration matrix, in contrast with more traditional iterative solvers which are known to exhibit poor convergence rates when applied to nearly uncoupled problems. We consider conjugate gradient acceleration, and we experiment with different block partitionings and row reorderings of the rate matrix. The results of numerical experiments on a simple reliability model, carried out on the CRAY T3D massively parallel computer, are discussed. The test results point to the fact that this method is well suited for the parallel solution of nearly uncoupled Markov chains.