| Title:
|
Aggregation/disaggregation iterative methods applied to Leontev systems and Markov chains (English) |
| Author:
|
Marek, Ivo |
| Author:
|
Mayer, Petr |
| Language:
|
English |
| Journal:
|
Applications of Mathematics |
| ISSN:
|
0862-7940 (print) |
| ISSN:
|
1572-9109 (online) |
| Volume:
|
47 |
| Issue:
|
2 |
| Year:
|
2002 |
| Pages:
|
139-156 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
Leontev model |
| Keyword:
|
Markov chain |
| Keyword:
|
stochastic matrix |
| Keyword:
|
aggregation |
| Keyword:
|
stationary probability vector |
| MSC:
|
15A06 |
| MSC:
|
15A51 |
| MSC:
|
65C40 |
| MSC:
|
65F10 |
| idZBL:
|
Zbl 1090.15500 |
| idMR:
|
MR1894666 |
| DOI:
|
10.1023/A:1021785102298 |
| . |
| Date available:
|
2009-09-22T18:09:23Z |
| Last updated:
|
2020-07-02 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/134491 |
| . |
| Reference:
|
[1] W. L. Cao, W. J. Stewart: Iterative aggregation/disaggregation techniques for nearly uncoupled Markov chains.J. Assoc. Comput. Mach. 32 (1985), 702–719. MR 0796209, 10.1145/3828.214137 |
| Reference:
|
[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. |
| Reference:
|
[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. |
| Reference:
|
[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. |
| Reference:
|
[5] F. R. Gantmacher: The Theory of Matrices.Gos. Izd. Lit., Moscow, 1954. (Russian) |
| Reference:
|
[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) |
| Reference:
|
[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. |
| Reference:
|
[8] Š. Klapka, P. Mayer: Aggregation/disaggregation method for safety models.Appl. Math. 47 (2002), . MR 1894665 |
| Reference:
|
[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. MR 0745437, 10.1137/0605019 |
| Reference:
|
[10] U. Krieger: On iterative aggregation/disaggregation methods for finite Markov chains.Preprint Deutsche Bundespost Telekom, Research and Technology Centre, 1990. |
| Reference:
|
[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. |
| Reference:
|
[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. |
| Reference:
|
[13] I. Marek: Frobenius theory of positive operators. Comparison theorems and applications.SIAM J. Appl. Math. 19 (1970), 607–628. Zbl 0219.47022, MR 0415405, 10.1137/0119060 |
| Reference:
|
[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. MR 1640726, 10.1002/(SICI)1099-1506(199807/08)5:4<253::AID-NLA124>3.0.CO;2-B |
| Reference:
|
[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 |
| Reference:
|
[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 |
| Reference:
|
[17] : Matrix Market. A repository of test matrices of the National Institute of Standards and Technology.http://www math.nist.gov/MatrixMarket. |
| Reference:
|
[18] H. Nikaido: Convex Structures and Economic Theory.Academic Press, New York-London, 1968. Zbl 0172.44502, MR 0277233 |
| Reference:
|
[19] J. Ortega, W. Rheinboldt: Iterative Solution of Nonlinear Equations in Several Variables.Academic Press, New York, 1970. MR 0273810 |
| Reference:
|
[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. |
| Reference:
|
[21] W. J. Stewart: Introduction to the Numerical Solution of Markov Chains.Princeton University Press, Princeton, 1994. Zbl 0821.65099, MR 1312831 |
| Reference:
|
[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. |
| Reference:
|
[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. |
| Reference:
|
[24] R. S. Varga: Matrix Iterative Analysis.Prentice-Hall, Englewood Cliffs, 1962. MR 0158502 |
| . |
