A fast newton's iteration for M/G/1-type and GI/M/1-type Markov Chains

Juan F. Pérez, Miklós Telek, Benny Van Houdt

Producción científica: Contribución a una revistaArtículorevisión exhaustiva

7 Citas (Scopus)

Resumen

In this article we revisit Newton's iteration as a method to find the G or R matrix in M/G/1-type and GI/M/1-type Markov chains. We start by reconsidering the method proposed in Ref.[15], which required O(m 6+Nm 4) time per iteration, and show that it can be reduced to O(Nm 4), where m is the block size and N the number of blocks. Moreover, we show how this method is able to further reduce this time complexity to O(Nr 3+Nm 2r2+m 3r) when A 0 has rank r<m. In addition, we consider the case where [A 1A 2A N] is of rank r<m and propose a new Newton's iteration method which is proven to converge quadratically and that has a time complexity of O(Nm 3+Nm 2 r 2+mr 3) per iteration. The computational gains in all the cases are illustrated through numerical examples.

Idioma originalInglés estadounidense
Páginas (desde-hasta)557-583
Número de páginas27
PublicaciónStochastic Models
Volumen28
N.º4
DOI
EstadoPublicada - nov. 1 2012
Publicado de forma externa

Áreas temáticas de ASJC Scopus

  • Estadística y probabilidad
  • Modelización y simulación
  • Matemáticas aplicadas

Huella

Profundice en los temas de investigación de 'A fast newton's iteration for M/G/1-type and GI/M/1-type Markov Chains'. En conjunto forman una huella única.

Citar esto