Authors: Alexandru Lazari,
Lozovanu Dmitrii
Abstract
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$.
Vladimir Andrunachievic Institute of Mathematics
and Computer Science
5 Academiei str., Chisinau, MD−2028, Moldova
E-mail: ,
Fulltext

–
0.15 Mb