A fast newton's iteration for M/G/1-type and GI/M/1-type markov chains
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 t...
- Autores:
- Tipo de recurso:
- Fecha de publicación:
- 2012
- Institución:
- Universidad del Rosario
- Repositorio:
- Repositorio EdocUR - U. Rosario
- Idioma:
- eng
- OAI Identifier:
- oai:repository.urosario.edu.co:10336/27431
- Acceso en línea:
- https://doi.org/10.1080/15326349.2012.726038
https://repository.urosario.edu.co/handle/10336/27431
- Palabra clave:
- Markov chains
Matrix-anaytic methods
Newton iteration
Numerical methods for Markov chains
- Rights
- License
- Restringido (Acceso a grupos específicos)
| Summary: | 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 2 r 2 + m 3 r) when A 0 has rank r < m. In addition, we consider the case where [A 1 A 2…A 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. |
|---|