Necessary and sufficient conditions for global geometric convergence of block Gauss–Seidel iteration algorithm applied to Markov chains

Convergence properties of the block Gauss–Seidel algorithm applied to ergodic Markov chains are discussed in this paper. This algorithm is one of the most prevalent methods for computing ergodic probability vectors of large-scale Markov chains. We will provide necessary and sufficient conditions for global geometric convergence of this algorithm. To apply this algorithm, the state space of a Markov process is decomposed into mutually exclusive and exhaustive lumps. The convergence properties depend on this lumping. It is also shown that there exists at least one set of lumps, for any ergodic stochastic matrix, which assures geometric convergence of the algorithm.