Non-skip-free M/G/1-type Markov chains and Laurent matrix power series
type: Item
instance of: scholarly article
title: Non-skip-free M/G/1-type Markov chains and Laurent matrix power series
zbMATH Open document ID: 1055.65013
author: B. Meini
author: Dario A. Bini
published in: Linear Algebra and its Applications
publication date: 2004-08-04T00:00:00Z
review text: The problem of computing the steady state vector \(\pi P= \pi\), where \(P\) is a semi-infinite block matrix, is reduced to inverting a Laurent matrix power series \(A(z)\), which is singular for \(z= 1\), while this second problem is closely related to solving matrix equations and to computing the (block) weak Wiener-Hopf factorization of \(A(z)\), if it exists. The main purpose of this paper is to point out and investigate the computational problems on which is relying the utilization of non-skip-free (positive recurrent)Markov chains of the M/G/1-type, whose usefulness in queuing modelling is well-known. The authors prove for the beginning the equivalence of three related computational problems, i. e. computing Wiener Hopf factorizations, inverting Laurent matrix power series \(A(z)\), and solving power series matrix equations, and then they describe several algorithms devoted to solve these problems. The main computational difficulty is the singularity of the matrix \(A(z)\) for \(z= 1\), for which the authors define a new Laurent matrix power series \(A(z)\), which is singular in \(z= 0\), but analytic, invertible on a suitable domain, and whose solutions are more easily to be computed. Briefly, Section 2 demonstrates the relationship between the problems of solving matrix equations, computing the formal inverse, and the Wiener-Hopf factorization of the Laurent matrix power series \(A(z)\). Section 3 presents how to remove the singularity of the matrix \(A(z)\) at \(z= 1\) by replacing \(A(z)\) with a new matrix function \(\widehat A(z)\) that is singular at \(z= 0\) and in the same points of singularity of \(A(z)\) except for \(z =1\). Section 4 shows a generalized Ramaswami formula for the computation of the steady state vector \(\pi\), describes new algorithms for implementing the new approach, and addresses open problems. Section 5 contains numerical results and illustrates the effectiveness of the proposed method. Summarizing, the combination of the genera…
Mathematics Subject Classification ID: 65C40
Mathematics Subject Classification ID: 47A68
Mathematics Subject Classification ID: 60J22
Mathematics Subject Classification ID: 93C70
Mathematics Subject Classification ID: 65T50
zbMATH DE Number: 2081262
zbMATH Keywords: M/G/1 type Markov chains
zbMATH Keywords: Laurent matrix power series
zbMATH Keywords: Wiener-Hopf factorization
zbMATH Keywords: generalized Ramaswami formula
zbMATH Keywords: fast Fourier transform
zbMATH Keywords: queuing modelling
zbMATH Keywords: matrix equations
zbMATH Keywords: algorithms
describes a project that uses: na12
MaRDI profile type: Publication
full work available at URL: j.laa.2004.02.022
OpenAlex ID: W1998194012
cites work: Q3657835
cites work: Computations with infinite Toeplitz matrices and polynomials
cites work: Q4422515
cites work: On the Solution of a Nonlinear Matrix Equation Arising in Queueing Problems
cites work: Improved cyclic reduction for solving queueing problems
cites work: Q4314299
cites work: Introduction to large truncated Toeplitz matrices
cites work: An analysis of a class of telecommunications models
cites work: Spectral analysis of M/G/1 and G/M/1 type Markov chains
cites work: Non-Skip-Free M/G/1 and G/M/1 Type Markov Chains
cites work: Computation of Steady-State Probabilities for Infinite-State Markov Chains with Repeating Rows
cites work: Equilibrium distribution of block-structured Markov chains with repeating rows
cites work: Numerical Solutions of the Waiting Time Distribution and Idle Time Distribution of the Arithmetic GI/G/1 Queue
cites work: Waiting time, busy periods and output models of a server analyzed via Wiener–Hopf factorization
cites work: A shifted cyclic reduction algorithm for quasi-birth-death problems
cites work: Q4265495
cites work: Base tensorielle des matrices de Hankel (ou de Toeplitz). Applications
cites work: A logarithmic reduction algorithm for quasi-birth-death processes
cites work: Q4793342
cites work: An improved FFT-based version of Ramaswami's formula
cites work: Q5690353
cites work: Q4733209
cites work: A stable recursion for the steady state vector in markov chains of m/g/1 type
DOI: 10.1016/J.LAA.2004.02.022
description: scientific article; zbMATH DE number 2081262