STABILITY AND CONDITIONING ISSUES ON THE NUMERICAL
                       SOLUTION OF MARKOV CHAINS







                                 by

                            TUGRUL DAYAR




           A dissertation submitted to the Graduate Faculty of
                    North Carolina State University
                     in partial fulfillment of the
                     requirements of the Degree of 
                         Doctor of Philosophy





                          COMPUTER SCIENCE






                              Raleigh
                               1994







                           APPROVED BY:




           Yannis Viniotis               Carl D. Meyer    


           William J. Stewart            Harry G. Perros
     (Chair of Advisory Committee)








-------------------------------------------------------------------------------






                                ABSTRACT



DAYAR, TUGRUL. Stability and Conditioning Issues on the Numerical Solution

of Markov Chains. (Under the direction of William James Stewart.)

   Markovian modeling and analysis is extensively used in many disciplines

in evaluating the performance of existing systems and in analyzing and 

designing systems to be developed. In most cases the systems under 

consideration are large, and therefore require the employment of numerical

solution techniques. With the changing face of computing environments, there

are several issues that need to be addressed in the numerical solution of 

Markov chains. Firstly, stability and conditioning issues in the solution

of such large systems has to be of concern, and one should be in the 

lookout for algorithms that are more efficient and that produce more 

accurate results. This may be achieved by improving existing algorithms or

developing new ones that take advantage of the increased computer power.

In this thesis, the effects of using a modified version of Gaussian 

elimination in the iterative aggregation-disaggregation technique, which is

especially suited to the solution of ill-conditioned nearly completely

decomposable Markov chains, has been investigated. A second solution 

technique geared towards multivector computers has been extended to include

the systems of interest. A third solution technique, which is useful in

handling vast state spaces, is shown to be quite effective in computing

performance measures for systems having highly unbalanced stationary

probabilities. Experiments on real-life applications (involving mostly

large systems) have been conducted in each case. Finally, the possibility

of reducing the state space by combining states in nearly completely 

decomposable chains is discussed.