Volume 35, pp. 185-200, 2009.

Convergence issues in the theory and practice of iterative aggregation/disaggregation methods

Ivo Marek, Petr Mayer, and Ivana Pultarová

Abstract

Iterative aggregation/disaggregation (IAD) methods for the computation of stationary probability vectors of large scale Markov chains form efficient practical analysis tools. However, their convergence theory is still not developed appropriately. Furthermore, as in other multilevel methods such as multigrid methods, the number of relaxations on the fine level of the IAD algorithms which is to be executed plays a very important role. To better understand these methods, in this paper we study some new concepts as well as their behavior and dependence on the parameters involved in aggregation algorithms, and establish some necessary and/or sufficient conditions for convergence. The theory developed offers a proof of convergence of IAD algorithms independent of whether the governing iteration matrix is primitive or cyclic as one of its main results. Another important result concerns a comparison of the rates of convergence of two IAD processes. Some examples documenting the diversity of behavior of IAD methods are given.

Full Text (PDF) [176 KB]

Key words

Stationary probability vector of Markov chain, iterative aggregation/disaggregation

AMS subject classifications

15A15, 15A09, 15A23, 65F05

< Back