Iterative aggregation/disaggregation methods for computing some characteristics of Markov chains. II: Fast convergence.

*(English)*Zbl 1025.65012Summary: A class of iterative aggregation/disaggregation methods (IAD) for computation of some important characteristics of Markov chains such as stationary probability vectors and mean first passage times matrices is presented and convergence properties of the corresponding algorithms are analyzed. Particular attention is focused on the fast convergence. Some classes of problems are identified for which the IAD methods return exact solutions after one single iteration sweap.

For part I see I. Marek and P. Mayer, Lect. Notes Comput. Sci. 2179, 68–80 (2001; Zbl 1031.65020).

For part I see I. Marek and P. Mayer, Lect. Notes Comput. Sci. 2179, 68–80 (2001; Zbl 1031.65020).

##### MSC:

65C40 | Numerical analysis or methods applied to Markov chains |

60J22 | Computational methods in Markov chains |

##### Keywords:

finite Markov chains; stationary probability vectors; mean first passage; iterative aggregation/disaggregation methods; covariance matrix; convergence; algorithms##### Software:

MARCA
Full Text:
DOI

##### References:

[1] | Berman, A.; Plemmons, R.J., Nonnegative matrices in the mathematical sciences, (1979), Academic Press New York, reprinted by SIAM, Philadelphia, PA, 1994 · Zbl 0484.15016 |

[2] | Choi, H.; Szyld, D., Application of treshold partitioning of sparse matrices to Markov chains, (), 158-165 |

[3] | Courtois, P.J.; Semal, P., Block iterative algorithms for stochastic matrices, Linear algebra appl., 76, 59-80, (1986) · Zbl 0612.65020 |

[4] | T. Dayar, Permuting Markov chains to nearly completely decomposable form, SIAM J. Matrix Anal. Appl., to appear |

[5] | T. Dayar, W.J. Stewart, Comparison of partitioning techniques for two-level iterative solvers on large, sparse Markov chains, Tech. Rep. BU-CEIS-9805, Department of Computer Engineering and Information Science, Bilkent University, Ankara, Turkey, April 1998 · Zbl 0957.60076 |

[6] | Dayar, T.; Stewart, W.J., Comparison of partitioning techniques for two-level iterative solvers on large, sparse Markov chains, SIAM J. sci. comput., 21, 1691-1705, (2000) · Zbl 0957.60076 |

[7] | Koury, R.; McAllister, D.F.; Stewart, W.J., Methods for computing stationary distributions of nearly completely decomposable Markov chains, SIAM J. alg. disc. meth., 5, 2, 164-186, (1984) · Zbl 0605.60064 |

[8] | Gantmacher, F.R., The theory of matrices, English translation: applications of the theory of matrices, (1959), Interscience New York, (in Russian) · Zbl 0085.01001 |

[9] | Marek, I., Frobenius theory of positive operators. comparison theorems and applications, SIAM J. appl. math., 19, 607-628, (1970) · Zbl 0219.47022 |

[10] | Marek, I.; Mayer, P., Aggregation/disaggregation iterative methods applied to leontev and Markov chain models, Appl. math., 47, 131-156, (2001) |

[11] | I. Marek, P. Mayer, Aggregation/disaggregation methods for p-cyclic Markov chains, Comput. (2001) · Zbl 1002.65013 |

[12] | Marek, I.; Mayer, P., Convergence analysis of an aggregation/disaggregation iterative method for computation stationary probability vectors of stochastic matrices, Numer. linear algebra appl., 5, 253-274, (1998) · Zbl 0937.65047 |

[13] | Marek, I.; Mayer, P., Convergence theory of some classes of iterative aggregation/disaggregation methods for computing stationary probability vectors of stochastic matrices, Laa, 363, 177-200, (2003) · Zbl 1018.65048 |

[14] | Marek, I.; Mayer, P., Iterative aggregation/disaggregation methods for computing some characteristics of Markov chains, () · Zbl 1031.65020 |

[15] | Marek, I.; Mayer, P., Iterative aggregation/disaggregation methods for computing stationary probability vectors of stochastic matrices can be finitely terminating, J. differential equations appl., 3, 301-313, (2001) · Zbl 1045.65031 |

[16] | Ortega, J.; Rheinboldt, W., Iterative solution of nonlinear equations in several variables, (1970), Academic Press New York · Zbl 0241.65046 |

[17] | Stewart, W.J., Introduction to the numerical solution of Markov chains, (1994), Princeton University Press Princeton, NJ · Zbl 0821.65099 |

[18] | H. Vantilborgh, The error aggregation. A contribution to the theory of decomposable systems and applications, Ph.D. Thesis, Faculty of Applied Sciences, Louvain Catholic University, Louvain-la Neuve, Belgium, 1981 |

[19] | Varga, R.S., Matrix iterative analysis, (1962), Prentice-Hall Englewood Cliffs, NJ · Zbl 0133.08602 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.