Marek, Ivo Iterative aggregation/disaggregation methods for computing some characteristics of Markov chains. II: Fast convergence. (English) Zbl 1025.65012 Appl. Numer. Math. 45, No. 1, 11-28 (2003). Summary: 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). Cited in 6 Documents 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 Citations:Zbl 1031.65020 Software:MARCA PDFBibTeX XMLCite \textit{I. Marek}, Appl. Numer. Math. 45, No. 1, 11--28 (2003; Zbl 1025.65012) Full Text: DOI References: [1] Berman, A.; Plemmons, R. J., Nonnegative Matrices in the Mathematical Sciences (1979), Academic Press: 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, (Proceedings of the IEEE International Computer Performance and Dependability Symposium IPDS ’96, Urbana, IL (1996)), 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; 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; 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), Gos. Izdatelstvo: Gos. Izdatelstvo Moscow: Interscience: Gos. Izdatelstvo: Gos. Izdatelstvo Moscow: 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); 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, (Margenov, S.; Wasniewski, J.; Yalamov, P., Large-Scale Scientific Computing, Third International Conference, LJSC 2001, Sozopol, Bulgaria, June 2001, LNCS, 2179 (2001), Springer: Springer Berlin) · 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: Academic Press New York · Zbl 0241.65046 [17] Stewart, W. J., Introduction to the Numerical Solution of Markov Chains (1994), Princeton University Press: 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; 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: 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.