SIAM JOURNAL ON SCIENTIFIC COMPUTING, VOL.19, NO.1, PP.148-154, 1998. 

TITLE: State Space Orderings for Gauss-Seidel in Markov Chains Revisited

AUTHOR: Tugrul Dayar 

ABSTRACT: States of a Markov chain may be reordered to reduce the magnitude 
of the subdominant eigenvalue of the Gauss-Seidel (GS) iteration matrix. 
Orderings that maximize the elemental mass or the number of nonzero elements 
in the dominant term of the GS splitting (that is, the term approximating 
the coefficient matrix) do not necessarily converge faster. An ordering of a 
Markov chain that satisfies Property-R is semi-convergent. On the other 
hand, there are semi-convergent state space orderings that do not satisfy 
Property-R. For a given ordering, a simple approach for checking Property-R 
is shown. Moreover, a version of the Cuthill-McKee algorithm may be used to 
order the states of a Markov chain so that Property-R is satisfied. The 
computational complexity of the ordering algorithm is less than that of a 
single GS iteration. In doing all this, the aim is to gain an insight for 
(faster) converging orderings.

KEY WORDS: State space ordering, Markov chains, Gauss-Seidel, Property-R,
Cuthill-McKee algorithm