Geodesic
New algorithms for finding the limiting and differential matrices in Markov chains
Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica, no. 1 (2020), pp. 75-88 
Alexandru Lazari; Dmitrii Lozovanu. New algorithms for finding the limiting and differential matrices in Markov chains. Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica, no. 1 (2020), pp. 75-88. http://geodesic.mathdoc.fr/item/BASM_2020_1_a4/
@article{BASM_2020_1_a4,
     author = {Alexandru Lazari and Dmitrii Lozovanu},
     title = {New algorithms for finding the limiting and differential matrices in {Markov} chains},
     journal = {Buletinul Academiei de \c{S}tiin\c{t}e a Republicii Moldova. Matematica},
     pages = {75--88},
     year = {2020},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/BASM_2020_1_a4/}
}
TY  - JOUR
AU  - Alexandru Lazari
AU  - Dmitrii Lozovanu
TI  - New algorithms for finding the limiting and differential matrices in Markov chains
JO  - Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica
PY  - 2020
SP  - 75
EP  - 88
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/BASM_2020_1_a4/
LA  - en
ID  - BASM_2020_1_a4
ER  - 
%0 Journal Article
%A Alexandru Lazari
%A Dmitrii Lozovanu
%T New algorithms for finding the limiting and differential matrices in Markov chains
%J Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica
%D 2020
%P 75-88
%N 1
%U http://geodesic.mathdoc.fr/item/BASM_2020_1_a4/
%G en
%F BASM_2020_1_a4

Voir la notice de l'article provenant de la source Math-Net.Ru

New algorithms for determining the limiting and differential matrices in Markov chains, using fast matrix multiplication methods, new computation procedure of the characteristic polynomial and algorithms of resuming matrix polynomials, are proposed. We show that the complexity of finding the limiting matrix is $O(n^3)$ and the complexity of calculating differential matrices is $O(n^{\omega+1})$, where $n$ is the number of the states of the Markov chain and $O(n^\omega)$ is the complexity of the used matrix multiplication algorithm. The theoretical computational complexity estimation of the algorithm is governed by the fastest known matrix multiplication algorithm, for which $\omega2.372864$.

[1] Lozovanu D., Pickl S., Optimization of Stochastic Discrete Systems and Control on Complex Networks, Springer, 2015 | MR | Zbl

[2] Le Gall F., “Powers of tensors and fast matrix multiplication”, Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, 2014, 296–303 | DOI | MR | Zbl

[3] Williams V., Multiplying matrices in $O(n^{2.373})$ time, Stanford University, 2014

[4] Alonso P., Boratto M., Peinado J., Ibáñez J., Sastre J., On the evaluation of matrix polynomials using several GPGPUs, 2014

[5] Ballard G., Demmel J., Holtz O., Lipshitz B., Schwartz O., Communication-Optimal Parallel Algorithm for Strassen's Matrix Multiplication, Cornell University Library, 2012

[6] Lazari A., “Algorithms for determining the transient and differential matrices in finite Markov processes”, Bul. Acad. Ştiinţe Repub. Moldova, Mat., 2010, no. 2(63), 84–99 | MR | Zbl

[7] Lazari A., Lozovanu D., “An approach for determining the matrix of limiting state probabilities in discrete Markov processes”, Bul. Acad. Ştiinţe Repub. Moldova, Mat., 2010, no. 1(62), 77–91 | MR | Zbl

[8] Cormen T. H., Leiserson C. E., Rivest R. L., Stein C., Introduction to Algorithms, 3rd ed., MIT Press, Cambridge, MA, 2009 | MR | Zbl

[9] D'Alberto P., Nicolau A., Adaptive Winograd's Matrix Multiplications, ACM Transactions on Mathematical Software, V, 2008 | MR

[10] Pernet C., Storjohann A., Faster algorithms for the characteristic polynomial, N2L 3G1, David R. Cheriton School of Computer Science University of Waterloo, Ontario, Canada, 2007 | MR

[11] Bernstein D., Matrix Mathematics, Princeton University Press, 2005 | MR | Zbl

[12] WanZhen L., Roi B., Chandra S., Yihan S., Alexis T., Martin H., “Fast methods for resumming matrix polynomials and Chebyshev matrix polynomials”, Journal of Computational Physics, 194 (2004), 575–587 | DOI | MR | Zbl

[13] Puterman M., Markov Decision Processes: Discrete Stochastic Dynamic Programming, Wiley, 2005 | MR | Zbl

[14] Coppersmith D., Winograd S., “Matrix multiplication via arithmetic progressions”, J. Symbolic Computation, 9:3 (1990), 251–280 | DOI | MR | Zbl

[15] Keller-Gehrig W., “Fast algorithms for the characteristic polynomial”, Theoretical Computer Science, 36 (1985), 309–317 | DOI | MR | Zbl

[16] Strassen V., “Gaussian elimination is not optimal”, Numer. Math., 13 (1969), 354–356 | DOI | MR | Zbl

[17] Howard R. A., Dynamic Programming and Markov Processes, Wiley, 1960 | MR | Zbl