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...

Full description

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)
id EDOCUR2_68fddaaf3f6d566b9fb1749b8bc0d8ec
oai_identifier_str oai:repository.urosario.edu.co:10336/27431
network_acronym_str EDOCUR2
network_name_str Repositorio EdocUR - U. Rosario
repository_id_str
spelling 8003520260043f5fafc-000d-4cff-977c-8461c20adcda420ab075-a640-42a6-8323-60ddd335b3632020-08-19T14:42:10Z2020-08-19T14:42:10Z2012-11-06In 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.application/pdfhttps://doi.org/10.1080/15326349.2012.726038ISSN: 1532-6349EISSN: 1532-4214https://repository.urosario.edu.co/handle/10336/27431engThe Institute for Operations Research and the Management SciencesTaylor & Francis383No. 3357Stochastic ModelsVol. 26Stochastic Models, ISSN: 1532-6349;EISSN: 1532-4214, Vol.26, No.3 (2010); pp. 357–383https://www.tandfonline.com/doi/abs/10.1080/15326349.2012.726038Restringido (Acceso a grupos específicos)http://purl.org/coar/access_right/c_16ecStochastic Modelsinstname:Universidad del Rosarioreponame:Repositorio Institucional EdocURMarkov chainsMatrix-anaytic methodsNewton iterationNumerical methods for Markov chainsA fast newton's iteration for M/G/1-type and GI/M/1-type markov chainsUna iteración de newton rápida para cadenas de markov de tipo M / G / 1 y tipo GI / M / 1articleArtículohttp://purl.org/coar/version/c_970fb48d4fbd8a85http://purl.org/coar/resource_type/c_6501Pérez, Juan F.Telek, MiklósVan Houdt, Benny10336/27431oai:repository.urosario.edu.co:10336/274312021-09-23 12:29:47.186https://repository.urosario.edu.coRepositorio institucional EdocURedocur@urosario.edu.co
dc.title.spa.fl_str_mv A fast newton's iteration for M/G/1-type and GI/M/1-type markov chains
dc.title.TranslatedTitle.spa.fl_str_mv Una iteración de newton rápida para cadenas de markov de tipo M / G / 1 y tipo GI / M / 1
title A fast newton's iteration for M/G/1-type and GI/M/1-type markov chains
spellingShingle A fast newton's iteration for M/G/1-type and GI/M/1-type markov chains
Markov chains
Matrix-anaytic methods
Newton iteration
Numerical methods for Markov chains
title_short A fast newton's iteration for M/G/1-type and GI/M/1-type markov chains
title_full A fast newton's iteration for M/G/1-type and GI/M/1-type markov chains
title_fullStr A fast newton's iteration for M/G/1-type and GI/M/1-type markov chains
title_full_unstemmed A fast newton's iteration for M/G/1-type and GI/M/1-type markov chains
title_sort A fast newton's iteration for M/G/1-type and GI/M/1-type markov chains
dc.subject.keyword.spa.fl_str_mv Markov chains
Matrix-anaytic methods
Newton iteration
Numerical methods for Markov chains
topic Markov chains
Matrix-anaytic methods
Newton iteration
Numerical methods for Markov chains
description 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.
publishDate 2012
dc.date.created.spa.fl_str_mv 2012-11-06
dc.date.accessioned.none.fl_str_mv 2020-08-19T14:42:10Z
dc.date.available.none.fl_str_mv 2020-08-19T14:42:10Z
dc.type.eng.fl_str_mv article
dc.type.coarversion.fl_str_mv http://purl.org/coar/version/c_970fb48d4fbd8a85
dc.type.coar.fl_str_mv http://purl.org/coar/resource_type/c_6501
dc.type.spa.spa.fl_str_mv Artículo
dc.identifier.doi.none.fl_str_mv https://doi.org/10.1080/15326349.2012.726038
dc.identifier.issn.none.fl_str_mv ISSN: 1532-6349
EISSN: 1532-4214
dc.identifier.uri.none.fl_str_mv https://repository.urosario.edu.co/handle/10336/27431
url https://doi.org/10.1080/15326349.2012.726038
https://repository.urosario.edu.co/handle/10336/27431
identifier_str_mv ISSN: 1532-6349
EISSN: 1532-4214
dc.language.iso.spa.fl_str_mv eng
language eng
dc.relation.citationEndPage.none.fl_str_mv 383
dc.relation.citationIssue.none.fl_str_mv No. 3
dc.relation.citationStartPage.none.fl_str_mv 357
dc.relation.citationTitle.none.fl_str_mv Stochastic Models
dc.relation.citationVolume.none.fl_str_mv Vol. 26
dc.relation.ispartof.spa.fl_str_mv Stochastic Models, ISSN: 1532-6349;EISSN: 1532-4214, Vol.26, No.3 (2010); pp. 357–383
dc.relation.uri.spa.fl_str_mv https://www.tandfonline.com/doi/abs/10.1080/15326349.2012.726038
dc.rights.coar.fl_str_mv http://purl.org/coar/access_right/c_16ec
dc.rights.acceso.spa.fl_str_mv Restringido (Acceso a grupos específicos)
rights_invalid_str_mv Restringido (Acceso a grupos específicos)
http://purl.org/coar/access_right/c_16ec
dc.format.mimetype.none.fl_str_mv application/pdf
dc.publisher.spa.fl_str_mv The Institute for Operations Research and the Management Sciences
Taylor & Francis
dc.source.spa.fl_str_mv Stochastic Models
institution Universidad del Rosario
dc.source.instname.none.fl_str_mv instname:Universidad del Rosario
dc.source.reponame.none.fl_str_mv reponame:Repositorio Institucional EdocUR
repository.name.fl_str_mv Repositorio institucional EdocUR
repository.mail.fl_str_mv edocur@urosario.edu.co
_version_ 1814167529735585792