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

Resultado de la investigación: Contribución a una revistaArtículo

3 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

Huella dactilar

Newton Iteration
Newton-Raphson method
Markov processes
Markov chain
Time Complexity
Iteration
R-matrix
Iteration Method
Newton Methods
Converge
Numerical Examples

All Science Journal Classification (ASJC) codes

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

Citar esto

Pérez, Juan F. ; Telek, Miklós ; Van Houdt, Benny. / A fast newton's iteration for M/G/1-type and GI/M/1-type Markov Chains. En: Stochastic Models. 2012 ; Vol. 28, N.º 4. pp. 557-583.
@article{8e5981cd0eb3451e837d28a72973af97,
title = "A fast newton's iteration for M/G/1-type and GI/M/1-type Markov Chains",
abstract = "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 rA 2A N] is of rank r3+Nm 2 r 2+mr 3) per iteration. The computational gains in all the cases are illustrated through numerical examples.",
author = "P{\'e}rez, {Juan F.} and Mikl{\'o}s Telek and {Van Houdt}, Benny",
year = "2012",
month = "11",
day = "1",
doi = "10.1080/15326349.2012.726038",
language = "English (US)",
volume = "28",
pages = "557--583",
journal = "Stochastic Models",
issn = "1532-6349",
publisher = "Taylor and Francis Ltd.",
number = "4",

}

A fast newton's iteration for M/G/1-type and GI/M/1-type Markov Chains. / Pérez, Juan F.; Telek, Miklós; Van Houdt, Benny.

En: Stochastic Models, Vol. 28, N.º 4, 01.11.2012, p. 557-583.

Resultado de la investigación: Contribución a una revistaArtículo

TY - JOUR

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

AU - Pérez, Juan F.

AU - Telek, Miklós

AU - Van Houdt, Benny

PY - 2012/11/1

Y1 - 2012/11/1

N2 - 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 rA 2A N] is of rank r3+Nm 2 r 2+mr 3) per iteration. The computational gains in all the cases are illustrated through numerical examples.

AB - 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 rA 2A N] is of rank r3+Nm 2 r 2+mr 3) per iteration. The computational gains in all the cases are illustrated through numerical examples.

UR - http://www.scopus.com/inward/record.url?scp=84869829521&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84869829521&partnerID=8YFLogxK

U2 - 10.1080/15326349.2012.726038

DO - 10.1080/15326349.2012.726038

M3 - Article

AN - SCOPUS:84869829521

VL - 28

SP - 557

EP - 583

JO - Stochastic Models

JF - Stochastic Models

SN - 1532-6349

IS - 4

ER -