Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Bul. Acad. Ştiinţe Repub. Mold. Mat.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica, 2020, Number 1, Pages 75–88 (Mi basm524)  

Research articles

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

Alexandru Lazari, Dmitrii Lozovanu

Vladimir Andrunachievic Institute of Mathematics and Computer Science, 5 Academiei str., Chişinău, MD-2028, Moldova
References:
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$.
Keywords and phrases: discrete markov process, the matrix of limiting states probabilities, differential matrices, matrix multiplication complexity.
Received: 04.03.2020
Document Type: Article
Language: English
Citation: Alexandru Lazari, Dmitrii Lozovanu, “New algorithms for finding the limiting and differential matrices in Markov chains”, Bul. Acad. Ştiinţe Repub. Mold. Mat., 2020, no. 1, 75–88
Citation in format AMSBIB
\Bibitem{LazLoz20}
\by Alexandru~Lazari, Dmitrii~Lozovanu
\paper New algorithms for finding the limiting and differential matrices in Markov chains
\jour Bul. Acad. \c Stiin\c te Repub. Mold. Mat.
\yr 2020
\issue 1
\pages 75--88
\mathnet{http://mi.mathnet.ru/basm524}
Linking options:
  • https://www.mathnet.ru/eng/basm524
  • https://www.mathnet.ru/eng/basm/y2020/i1/p75
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica
    Statistics & downloads:
    Abstract page:102
    Full-text PDF :63
    References:12
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024