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 

AMS SUBJECT CLASSIFICATIONS: 65U05, 60J10, 60J27, 65F10, 65F50, 65F30, 65B99