SIAM JOURNAL ON SCIENTIFIC COMPUTING, VOL.17, NO.1, PP.287-303, 1996.

TITLE: On the Effects of Using the Grassmann-Taksar-Heyman Method in Iterative 
       Aggregation-Disaggregation

AUTHORS: Tugrul Dayar and William J. Stewart

ABSTRACT: Iterative aggregation-disaggregation (IAD) is an effective method 
for solving finite nearly completely decomposable (NCD) Markov chains. Small 
perturbations in the transition probabilities of these chains may lead to 
considerable changes in the stationary probabilities; NCD Markov chains are 
known to be ill-conditioned. During an IAD step, this undesirable condition is 
inherited by the coupling matrix and one confronts the problem of finding the 
stationary probabilities of a stochastic matrix whose diagonal elements are 
close to 1. In this paper, the effects of using the Grassmann-Taksar-Heyman 
(GTH) method to solve the coupling matrix formed in the aggregation step is 
investigated. Then, the idea is extended in such a way that the same direct 
method can be incorporated into the disaggregation step. Finally, the effects 
of using the GTH method in the IAD algorithm on various examples are
demonstrated, and the conditions under which it should be employed are 
explained.

KEY WORDS: Markov chains, decomposability, stationary probability, 
aggregation-disaggregation, Gaussian elimination, sparsity schemes 

AMS SUBJECT CLASSIFICATIONS: 60J10, 60J27, 65F05, 65F10, 60-04