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

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

Research output: Contribution to journalArticlepeer-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 languageEnglish (US)
Pages (from-to)279-302
Number of pages24
JournalStochastic Models
Volume21
Issue number2-3
DOIs
StatePublished - 2005

Keywords

  • Canonical factorization
  • Cyclic reduction
  • Markov chains
  • Matrix equations
  • Shift technique

ASJC Scopus subject areas

  • Statistics and Probability
  • Modeling and Simulation
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Shift techniques and canonical factorizations in the solution of M/G/1-type markov chains'. Together they form a unique fingerprint.

Cite this