RO EN
New Algorithms for Finding the Limiting and Differential Matrices in Markov Chains
Authors: Alexandru Lazari, Lozovanu Dmitrii
– 0.15 Mb
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: ,
and Computer Science
5 Academiei str., Chisinau, MD−2028, Moldova
E-mail: ,
Fulltext
– 0.15 Mb
Contents
- Commutator subgroup of Sylow 2-subgroups of alternating group and the commutator width in the wreath product
- On two stability types for a multicriteria integer linear programming problem
- Closure operators in modules and their characterizations
- On the number of topologies on countable skew fields
- New Algorithms for Finding the Limiting and Differential Matrices in Markov Chains
- Solution of the problem of the center for cubic differential systems with three affine invariant straight lines of total algebraic multiplicity four
- On self-adjoint and invertible linear relations generated by integral equations
- Loops with invariant flexibility under the isostrophy
