Title
A fast Newton's iteration for M/G/1-type and GI/M/1-type Markov chainsA fast Newton's iteration for M/G/1-type and GI/M/1-type Markov chains
Author
Faculty/Department
Faculty of Sciences. Mathematics and Computer Science
Research group
Modeling Of Systems and Internet Communication (MOSAIC)
Publication type
article
Publication
New York, N.Y.,
Subject
Mathematics
Source (journal)
Stochastic models. - New York, N.Y.
Volume/pages
28(2012):4, p. 557-583
ISSN
1532-6349
ISI
000310849700002
Carrier
E
Target language
English (eng)
Full text (Publishers DOI)
Affiliation
University of Antwerp
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(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.
Full text (open access)
https://repository.uantwerpen.be/docman/irua/843bab/4390.pdf
E-info
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000310849700002&DestLinkType=RelatedRecords&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000310849700002&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000310849700002&DestLinkType=CitingArticles&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
Handle