Access Restriction

Author Cao, Wei-Lu ♦ Stewart, William J.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1985
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract Iterative aggregation/disaggregation methods provide an efficient approach for computing the stationary probability vector of nearly uncoupled (also known as nearly completely decomposable) Markov chains. Three such methods that have appeared in the literature recently are considered and their similarities and differences are outlined. Specifically, it is shown that the method of Takahashi corresponds to a modified block Gauss-Seidel step and aggregation, whereas that of Vantilborgh corresponds to a modified block Jacobi step and aggregation. The third method, that of Koury et al., is equivalent to a standard block Gauss-Seidel step and iteration. For each of these methods, a lemma is established, which shows that the unique fixed point of the iterative scheme is the left eigenvector corresponding to the dominant unit eigenvalue of the stochastic transition probability matrix. In addition, conditions are established for the convergence of the first two of these methods; convergence conditions for the third having already been established by Stewart et al. All three methods are shown to have the same asymptotic rate of convergence.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1985-07-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 32
Issue Number 3
Page Count 18
Starting Page 702
Ending Page 719

Open content in new tab

   Open content in new tab
Source: ACM Digital Library