Premium
A divide and conquer approach to computing the mean first passage matrix for Markov chains via Perron complement reductions
Author(s) -
Kirkland Stephen J.,
Neumann Michael,
Xu Jianhong
Publication year - 2001
Publication title -
numerical linear algebra with applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.02
H-Index - 53
eISSN - 1099-1506
pISSN - 1070-5325
DOI - 10.1002/nla.242
Subject(s) - mathematics , markov chain , flops , block matrix , partition (number theory) , matrix multiplication , combinatorics , ergodic theory , complement (music) , matrix (chemical analysis) , divide and conquer algorithms , diagonal , discrete mathematics , computation , algorithm , parallel computing , computer science , pure mathematics , materials science , chemistry , composite material , quantum , biochemistry , geometry , quantum mechanics , eigenvalues and eigenvectors , statistics , physics , complementation , gene , phenotype
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.