A logarithmic reduction algorithm for quasi-birth-death processes

DOI10.2307/3214773zbMath0789.60055OpenAlexW2070689535MaRDI QIDQ4274457

Vaidyanathan Ramaswami, Guy Latouche

Publication date: 25 May 1994

Published in: Journal of Applied Probability (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/3214773

zbMATH Keywords

numerical examples quadratic convergence minimal nonnegative solutions quasi-birth-death processes irreducible chain

Mathematics Subject Classification ID

Discrete-time Markov processes on general state spaces (60J05) Queueing theory (aspects of probability theory) (60K25) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Probabilistic methods, stochastic differential equations (65C99)

Related Items

Comparing Some Algorithms for Solving QBD Processes Exhibiting Special Structures ⋮ Analysis and optimization of hybrid replenishment policy in a double-sources queueing-inventory system with MAP arrivals ⋮ Erlangian Approximations for the Transient Analysis of a Fluid Queue Model for Forest Fire Perimeter ⋮ An inventory system with replacement and refurbishment of failed items ⋮ Modelling of a $\mathrm{MAP/PH(1)}$, $\mathrm{PH}(2)/2$ production inventory system with multiple servers and production vacations ⋮ Unnamed Item ⋮ Nonlinear matrix equations and structured linear algebra ⋮ On the solution of algebraic Riccati equations arising in fluid queues ⋮ Solving nonlinear matrix equations arising in tree-like stochastic processes. ⋮ Optimal Routing Among ⋅/M/1 Queues with Partial Information ⋮ Two Types ofRG-Factorizations of Quasi-birth-and-death Processes and Their Applications to Stochastic Integral Functionals ⋮ An $M/M/1$ queueing-inventory system with working vacations, vacation interruptions and lost sales ⋮ Efficient computation of the extreme solutions of $X+A^*X^{-1}A=Q$ and $X-A^*X^{-1}A=Q$ ⋮ $\mathrm{MAP}/\mathrm{M}/c$ and $\mathrm{M}/\mathrm{PH}/c$ queues with constant impatience times ⋮ Quasi-Birth-and-Death Processes with an Explicit Rate Matrix ⋮ Transient Analysis of Fluid Models via Elementary Level-Crossing Arguments ⋮ A proof of the steepest increase conjecture of a phase-type density ⋮ ON LATOUCHE–RAMASWAMI'S LOGARITHMIC REDUCTION ALGORITHM FOR QUASI-BIRTH-AND-DEATH PROCESSES ⋮ A multi-server queueing model with server consultations ⋮ Wavelet transform for quasi-birth-death process with a continuous phase set ⋮ Unnamed Item ⋮ Shared-object system equilibria: delay and throughput analysis ⋮ Computations with infinite Toeplitz matrices and polynomials ⋮ On the analysis of the Gerber-Shiu discounted penalty function for risk processes with Markovian arrivals ⋮ Optimal routing in two parallel queues with exponential service times ⋮ Analysis of semi-open queueing networks using lost customers approximation with an application to robotic mobile fulfilment systems ⋮ Breaking the dimensionality curse in multi-server queues ⋮ An application of deterministic chaotic maps to model packet traffic ⋮ Passage times in fluid models with application to risk processes ⋮ An efficient solution to a retrial queue for the performability evaluation of DHCP ⋮ A probabilistic algorithm for finding the rate matrix of a block-GI/M/1 Markov chain ⋮ A probabilistic algorithm for determining the fundamental matrix of a block M/G/1 Markov chain ⋮ Condition numbers and backward error of a matrix polynomial equation arising in stochastic models ⋮ A numerically efficient method for the $MAP/D/1/K$ queue via rational approximations ⋮ A multi-server synchronous vacation model with thresholds and a probabilistic decision rule ⋮ Exploiting the Toeplitz structure in certain queueing problems ⋮ Computational procedures for a class of GI/D/$k$ systems in discrete time ⋮ A multi-server queueing system with service interruption, partial protection and repetition of service ⋮ A perishable inventory system with service facility and feedback customers ⋮ Multiserver retrial queue with setup time and its application to data centers ⋮ Weight splitting iteration methods to solve quadratic nonlinear matrix equation $MY^2+NY+P=0$ ⋮ DES AND RES PROCESSES AND THEIR EXPLICIT SOLUTIONS ⋮ An approximation for kanban controlled assembly systems ⋮ Convergence of pure and relaxed Newton methods for solving a matrix polynomial equation arising in stochastic models ⋮ The Erlangization method for Markovian fluid flows ⋮ Generalized parallel-server fork-join queues with dynamic task scheduling ⋮ A QBD approach to evolutionary game theory ⋮ The UnreliableM/M/1 Retrial Queue in a Random Environment ⋮ Queues with boundary assistance: The effects of truncation ⋮ Non-skip-free M/G/1-type Markov chains and Laurent matrix power series ⋮ Multiclass Markovian fluid queues ⋮ Efficient algorithms for transient analysis of stochastic fluid flow models ⋮ Stationary Distributions of Continuous-Time Markov Chains: A Review of Theory and Truncation-Based Approximations ⋮ The variance constant for continuous-time level dependent quasi-birth-and-death processes ⋮ An IBNR-RBNS insurance risk model with marked Poisson arrivals ⋮ Time to congestion in homogeneous quasi-birth-and-death processes. ⋮ Continuous-time QBD processes with continuous phase variable ⋮ An auxiliary server threshold queueing model and its application to the operational characteristics of web server system ⋮ Analysis of a multiserver queueing-inventory system ⋮ On the Dual Relationship Between Markov Chains of GI/M/1 and M/G/1 Type ⋮ Sojourn times in a two-stage queueing network with blocking ⋮ Ramaswami's duality and probabilistic algorithms for determining the rate matrix for a structured GI/M/1 Markov chain ⋮ On the optimal control of manufacturing and remanufacturing activities with a single shared server ⋮ $M/M/s$ queue with impatient customers and retrials ⋮ Steady state analysis of level dependent quasi-birth-and-death processes with catastrophes ⋮ Deviation matrix and asymptotic variance for $\mathrm{GI}/\mathrm{M}/1$-type Markov chains ⋮ Truncation and augmentation of level-independent QBD processes. ⋮ Algorithms for Markov stochastic models ⋮ Efficient methods for solving a nonsymmetric algebraic Riccati equation arising in stochastic fluid models ⋮ Transforming algebraic Riccati equations into unilateral quadratic matrix equations ⋮ Fluid Flow Models and Queues—A Connection by Stochastic Coupling ⋮ Analysis of multiserver queues with constant retrial rate ⋮ Solving matrix polynomial equations arising in queueing problems ⋮ On bulk-service MAP/PH$^{L,N}$/1/N G-queues with repeated attempts ⋮ A catastrophic queueing model with delayed action ⋮ CSL model checking algorithms for QBDs ⋮ A transient analysis of Markov fluid models with jumps ⋮ Algorithmic analysis of the MAP/PH/1 retrial queue ⋮ AMAP/G/1 Queue with an Underlying Birth–Death Process ⋮ A probabilistic interpretation of cyclic reduction and its relationships with logarithmic reduction ⋮ Shift Techniques and Canonical Factorizations in the Solution of M/G/1-Type Markov Chains ⋮ Phase-type distributions and representations: Some results and open problems for system theory ⋮ Risk processes analyzed as fluid queues ⋮ ANALYSIS OF A MULTI-SERVER QUEUE WITH MARKOVIAN ARRIVALS AND SYNCHRONOUS PHASE TYPE VACATIONS ⋮ Transient Analysis of Fluid Flow Models via Stochastic Coupling to a Queue ⋮ Analyzing $E_k/E_r/ c$ queues ⋮ Relaxed functional iteration techniques for the numerical solution of $M/G/1$ type Markov chains ⋮ Characterization of the departure process from anME/ME/1queue ⋮ The cyclic reduction algorithm: From Poisson equation to stochastic processes and beyond. In memoriam of Gene H. Golub ⋮ A $BMAP| G| 1$-analysis based on convolution calculus ⋮ Single-server queues under overdispersion in the heavy-traffic regime ⋮ Marked Markovian arrivals in a tandem G-network with blocking ⋮ Quasi-birth-and-death Markov processes with a tree structure and the MMAP[K/PH[K]/N/LCFS non-preemptive queue] ⋮ Analysis of a versatile multi-class delay-loss system with a superimposed Markovian arrival process ⋮ Highly accurate doubling algorithm for quadratic matrix equation from quasi-birth-and-death process ⋮ The M/M/c with critical jobs ⋮ Bayesian analysis of $Er/M/1$ and $Er/M/c$ queues ⋮ Age process, workload process, sojourn times, and waiting times in a discrete time SM[K/PH[K]/1/FCFS queue] ⋮ Analysis of nonpreemptive priority queues with multiple servers and two priority classes ⋮ A general theory on spectral properties of state-homogeneous finite-state quasi-birth-death processes ⋮ Highly Accurate Latouche-Ramaswami Logarithmic Reduction Algorithm for Quasi-Birth-and-Death Process ⋮ On a Customer-Induced Interruption in a Service System ⋮ Analysis of MAP(1), MAP(2)/ PH/ 1 non-preemptive priority queueing model under classical retrial policy with breakdown, repair, discouragement, single vacation, standby server, negative arrival and impatient customers ⋮ A matrix-geometric approximation for tandem queues with blocking and repeated attempts ⋮ Discrete time queues and matrix-analytic methods. (With comments and rejoinder)