TITLE: Investigation of Numerical Solution Methods for Computing the
       Stationary Distribution of Markov Chains

PRINCIPAL INVESTIGATOR: Tugrul Dayar, Ph.D.

OTHER RESEARCHER: Wael Gueaieb, B.S.

INSTITUTION: Bilkent University, Department of Computer Engineering

SUPPORT: The Scientific and Technical Research Council of Turkey (TUBITAK)

AMOUNT: ~10,000 USD

DURATION: 15 August 1995 - 15 August 1997

ABSTRACT: In this study, we investigate numerical solution methods for 
computing the stationary distribution of Markov chains. In doing that, we 
especially concentrate on ill-conditioned, nearly completely decomposable 
(NCD) systems and systems having large, sparse coefficient matrices which 
pose difficulties in the solution process.

First, using the fact that NCD Markov chains are quasi-lumpable, we show
how cheap lower and upper bounds on the stationary probability of each
NCD block may be computed. The study is motivated by a kind of state space
reduction technique. Under some circumstances, it is possible to compute 
the stationary probabilities of some NCD blocks exactly.

Besides, we compare the effects of using nonsymmetric skyline (NSK) and 
compact sparse row (CSR) formats on the Grassman-Taksar-Heyman (GTH)
algorithm, a modified version of Gaussian elimination (GE) for M-matrices
with higher accuracy. As part of this study, we carry out the Markovian
modeling of a pushout threshold scheme for an asynchronous transfer mode
(ATM) traffic queue under two classes of arrivals. In conclusion, we see 
that the CSR implementation of GE for the transposed system of equations, 
and the CSR implementation of the GTH algorithm for the nontransposed 
system of equations which stores the lower and upper-triangular factors 
respectively give the smallest solution times.

We also investigate the effects on the Gauss-Seidel (GS) iterative algorithm
of symmetrically permuting a Markov chain. Starting from the fact that an
ordering of a Markov chain with Property-R is semi-convergent, we present an 
algorithm that will symmetrically permute an irreducible Markov chain to a 
form satisfying Property-R. Numerical experiments confirm that orderings 
with Property-R guarantee at least a semi-converging GS iteration for those 
cases where the original ordering is non-converging.

Experimental results with Krylov subspace methods on Markov chains, 
especially the ill-conditioned NCD ones, are few.  We perform numerical 
experiments to help us understand the effect of the degree of coupling of 
NCD Markov chains and their nonzero structure on the convergence 
characteristics and space requirements of preconditioned Krylov subspace 
methods, and compare the results with those of two-level iterative solvers.
Experimental results show that in most of the test cases two-level 
iterative solvers are superior to Krylov subspace methods with the chosen 
preconditioners. For two-level iterative solvers, there are cases in which 
a straightforward partitioning of the coefficient matrix gives a faster 
solution than can be obtained using the NCD normal form.

KEY WORDS: Markov chains, stationary solution, near complete decomposability,
ill-conditioning, quasi-lumpability, storage formats, Grassmann-Taksar-Heyman 
algorithm, Property-R, ordering, Gauss-Seidel algorithm, Krylov subspace 
methods, preconditioning, two-level iterative solvers, partitioning.