New algorithms for finding the limiting and differential matrices in Markov chains

Alexandru Lazari ; Dmitrii Lozovanu

Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica, no. 1 (2020), pp. 75-88.

Résumé

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 $\omega 2.372864$.

Bibliographie

[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