Previous |  Up |  Next

Article

Keywords:
Leontev model; Markov chain; stochastic matrix; aggregation; stationary probability vector
Summary:
The paper surveys some recent results on iterative aggregation/disaggregation methods (IAD) for computing stationary probability vectors of stochastic matrices and solutions of Leontev linear systems. A particular attention is paid to fast IAD methods.
References:
[1] W. L. Cao, W. J. Stewart: Iterative aggregation/disaggregation techniques for nearly uncoupled Markov chains. J.  Assoc. Comput. Mach. 32 (1985), 702–719. DOI 10.1145/3828.214137 | MR 0796209
[2] H. Choi, D. Szyld: Application of threshold partitioning of sparse matrices to Markov chains. In: Proceedings of the IEEE International Computer Performance and Dependability Symposium IPDS’96, Urbana, 1996, pp. 158–165.
[3] 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, 1998.
[4] I. S. Duff, J. K.  Reid: An implementation of Tarjan’s algorithm for the block triangularization of a matrix. ACM Trans. Math. Software 4 (1978), 337–147.
[5] F. R.  Gantmacher: The Theory of Matrices. Gos. Izd. Lit., Moscow, 1954. (Russian)
[6] Š. Klapka, P. Mayer: Reliability modelling of safety equipments. In: Proceedings of Programs and Algorithms of Numerical Mathematics, Libverda, June 2000, Mathematical Institute of the Academy of Sciences of the Czech Republic, Prague, 2000, pp. 78–84. (Czech)
[7] Š. Klapka, P. Mayer: Some aspects of modelling railway safety. Proc. SANM’99, Nečtiny, I. Marek (ed.), University of West Bohemia, Plzeň, 1999, pp. 135–140.
[8] Š. Klapka, P. Mayer: Aggregation/disaggregation method for safety models. Appl. Math. 47 (2002), . MR 1894665
[9] R. Koury, D. F.  McAllister and W. J. Stewart: Methods for computing stationary distributions of nearly completely decomposable Markov chains. SIAM J. Alg. Disc. Meth. 5 (1984), 164–186. DOI 10.1137/0605019 | MR 0745437
[10] U. Krieger: On iterative aggregation/disaggregation methods for finite Markov chains. Preprint Deutsche Bundespost Telekom, Research and Technology Centre, 1990.
[11] U. Krieger: Numerical solution methods for large finite Markov chains. In: Performance and Reliability Evaluation, K. Hare et al. (eds.), R. Oldenbourg, Wien, 1994, pp. 267–318.
[12] S. T. Leutenegger, G. H. Horton: On the utility of the multi-level algorithm for the solution of nearly completely decomposable Markov chains. In: Proceedings of the Second Internationl Workshop on the Numerical Solution of Markov Chains, W. J. Stewart (ed.), Kluwer, Boston, 1995, pp. 425–442.
[13] I. Marek: Frobenius theory of positive operators. Comparison theorems and applications. SIAM J.  Appl. Math. 19 (1970), 607–628. DOI 10.1137/0119060 | MR 0415405 | Zbl 0219.47022
[14] I. Marek, P.  Mayer: Convergence analysis of an aggregation/disaggregation iterative method for computation stationary probability vectors of stochastic matrices. Numer. Linear Algebra Appl. 5 (1998), 253–274. DOI 10.1002/(SICI)1099-1506(199807/08)5:4<253::AID-NLA124>3.0.CO;2-B | MR 1640726
[15] I. Marek, P. Mayer: Convergence theory of a class of iterative aggregation/disaggregation methods for computing stationary probability vectors of stochastic matrices. Linear Algebra Appl. (2001), Submitted. MR 1969068
[16] I. Marek, P. Mayer: Iterative aggregation/disaggregation methods for computing stationary probability vectors of stochastic matrices can be finitely terminating. International Journal of Differential Equations 3 (2001), 301–313. MR 1848180
[17] Matrix Market. A repository of test matrices of the National Institute of Standards and Technology. http://www math.nist.gov/MatrixMarket.
[18] H. Nikaido: Convex Structures and Economic Theory. Academic Press, New York-London, 1968. MR 0277233 | Zbl 0172.44502
[19] J. Ortega, W. Rheinboldt: Iterative Solution of Nonlinear Equations in Several Variables. Academic Press, New York, 1970. MR 0273810
[20] G. W. Stewart, W. J. Stewart and D. F.  McAllister: A two stage iteration for solving nearly uncoupled Markov chains. In: IMA Volumes in Mathematics and Applications 60: Recent Advances in Iterative Methods, G. H. Golub, A. Greenbaum and M. Luskin (eds.), Springer Verlag, New York, 1994, pp. 201–216.
[21] W. J. Stewart: Introduction to the Numerical Solution of Markov Chains. Princeton University Press, Princeton, 1994. MR 1312831 | Zbl 0821.65099
[22] Y. Takahashi: A lumping method for numerical calculations of stationary distributions of Markov chains. Res. Rep. B-18, Dept. of Inf. Sci. Tokyo Inst. of Tech., Tokyo, Japan, June 1975.
[23] H. Vantilborgh: The error aggregation. A contribution to the theory of decomposable systems and applications. PhD Thesis, Faculty of Applied Sciences, Louvain Catholic University, Louvain-la Neuve, Belgium, 1981.
[24] R. S. Varga: Matrix Iterative Analysis. Prentice-Hall, Englewood Cliffs, 1962. MR 0158502
Partner of
EuDML logo