A divide and conquer approach to computing the mean first passage matrix for Markov chains via Perron complement reductions

Let M_T be the mean first passage matrix for an n‐state ergodic Markov chain with a transition matrix T. We partition T as a 2×2 block matrix and show how to reconstruct M_T efficiently by using the blocks of T and the mean first passage matrices associated with the non‐overlapping Perron complements of T. We present a schematic diagram showing how this method for computing M_T can be implemented in parallel. We analyse the asymptotic number of multiplication operations necessary to compute M_T by our method and show that, for large size problems, the number of multiplications is reduced by about 1/8, even if the algorithm is implemented in serial. We present five examples of moderate sizes (of orders 20–200) and give the reduction in the total number of flops (as opposed to multiplications) in the computation of M_T. The examples show that when the diagonal blocks in the partitioning of T are of equal size, the reduction in the number of flops can be much better than 1/8. Copyright © 2001 John Wiley & Sons, Ltd.