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.