Shift techniques and canonical factorizations in the solution of M/G/1-type markov chains

Dario A. Bini; Beatrice Meini; Ilya M. Spitkovsky

doi:10.1081/STM-200056219

Shift techniques and canonical factorizations in the solution of M/G/1-type markov chains

Dario A. Bini, Beatrice Meini, Ilya M. Spitkovsky

Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

By using properties of canonical factorizations, we prove that under very mild assumptions, the shifted cyclic reduction method (SCR) can be applied for solving QBD problems with no breakdown and that it always converges. For general M/G/1 type Markov chains we prove that SCR always converges if no breakdown is encountered. Numerical experiments showing the acceleration provided by SCR versus cyclic reduction are presented.

Original language	English (US)
Pages (from-to)	279-302
Number of pages	24
Journal	Stochastic Models
Volume	21
Issue number	2-3
DOIs	https://doi.org/10.1081/STM-200056219
State	Published - 2005

Keywords

Canonical factorization
Cyclic reduction
Markov chains
Matrix equations
Shift technique

ASJC Scopus subject areas

Statistics and Probability
Modeling and Simulation
Applied Mathematics

Access to Document

10.1081/STM-200056219

Cite this

@article{de907b86872042eb9248678796edbf02,

title = "Shift techniques and canonical factorizations in the solution of M/G/1-type markov chains",

abstract = "By using properties of canonical factorizations, we prove that under very mild assumptions, the shifted cyclic reduction method (SCR) can be applied for solving QBD problems with no breakdown and that it always converges. For general M/G/1 type Markov chains we prove that SCR always converges if no breakdown is encountered. Numerical experiments showing the acceleration provided by SCR versus cyclic reduction are presented.",

keywords = "Canonical factorization, Cyclic reduction, Markov chains, Matrix equations, Shift technique",

author = "Bini, {Dario A.} and Beatrice Meini and Spitkovsky, {Ilya M.}",

note = "Funding Information: Received September 2004; Accepted February 2005 Address correspondence to Dario A. Bini, Dipartimento di Matematica, Universit{\`a} di Pisa, Pisa, Italy; E-mail: [email protected]. This work was partially supported by MIUR grant number 2002014121 and by GNCS-INDAM grant “Metodi numerici innovativi per il trattamento di matrici strutturate e sparse”. This work has been carried out while the Ilya M, Spitkovsky was visiting the University of Pisa under the support of GNCS of INDAM.",

year = "2005",

doi = "10.1081/STM-200056219",

language = "English (US)",

volume = "21",

pages = "279--302",

journal = "Stochastic Models",

issn = "1532-6349",

publisher = "Taylor and Francis Ltd.",

number = "2-3",

}

TY - JOUR

T1 - Shift techniques and canonical factorizations in the solution of M/G/1-type markov chains

AU - Bini, Dario A.

AU - Meini, Beatrice

AU - Spitkovsky, Ilya M.

N1 - Funding Information: Received September 2004; Accepted February 2005 Address correspondence to Dario A. Bini, Dipartimento di Matematica, Università di Pisa, Pisa, Italy; E-mail: [email protected]. This work was partially supported by MIUR grant number 2002014121 and by GNCS-INDAM grant “Metodi numerici innovativi per il trattamento di matrici strutturate e sparse”. This work has been carried out while the Ilya M, Spitkovsky was visiting the University of Pisa under the support of GNCS of INDAM.

PY - 2005

Y1 - 2005

N2 - By using properties of canonical factorizations, we prove that under very mild assumptions, the shifted cyclic reduction method (SCR) can be applied for solving QBD problems with no breakdown and that it always converges. For general M/G/1 type Markov chains we prove that SCR always converges if no breakdown is encountered. Numerical experiments showing the acceleration provided by SCR versus cyclic reduction are presented.

AB - By using properties of canonical factorizations, we prove that under very mild assumptions, the shifted cyclic reduction method (SCR) can be applied for solving QBD problems with no breakdown and that it always converges. For general M/G/1 type Markov chains we prove that SCR always converges if no breakdown is encountered. Numerical experiments showing the acceleration provided by SCR versus cyclic reduction are presented.

KW - Canonical factorization

KW - Cyclic reduction

KW - Markov chains

KW - Matrix equations

KW - Shift technique

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

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

U2 - 10.1081/STM-200056219

DO - 10.1081/STM-200056219

M3 - Article

AN - SCOPUS:27944471725

SN - 1532-6349

VL - 21

SP - 279

EP - 302

JO - Stochastic Models

JF - Stochastic Models

IS - 2-3

ER -

Shift techniques and canonical factorizations in the solution of M/G/1-type markov chains

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this