Semi-infinite quasi-Toeplitz matrices with applications to QBD stochastic processes

DOI10.1090/MCOM/3301MaRDI QIDQ3177717zbMATH OpenOpenAlexFDO

Authors Dario A. Bini, Stefano Massei, B. Meini

Publication date 1 August 2018

Published in Mathematics of Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1611.06337

zbMATH Keywords

Banach algebraquasi-Toeplitz matrixquasi-birth and death stochastic processes

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Matrix exponential and similar functions of matrices (15A16) Toeplitz, Cauchy, and related matrices (15B05) Numerical computation of matrix exponential and similar matrix functions (65F60)

Abstract: Denote by $mathcal{W}_1$ the set of complex valued functions of the form $a(z)=su{m}_{i=-infty}^{+infty}{a}_i{z}^i$ which are continuous on the unit circle, and such that $su{m}_{i=-infty}^{+infty}|i{a}_i|<infty$. We call CQT matrix a quasi-Toeplitz matrix $A$, associated with a continuous symbol $a(z)inmathcal{W}_1$, of the form $A=T(a)+E$, where $T(a)=(t_{i,j}{)}_{i,jinmathbb{Z}^{+}}$ is the semi-infinite Toeplitz matrix such that $t_{i,j}=a_{j-i}$, for $i,jinmathbb{Z}^{+}$, and $E=(e_{i,j}{)}_{i,jinmathbb{Z}^{+}}$ is a semi-infinite matrix such that $su{m}_{i,j=1}^{+infty}|e_{i,j}|$ is finite. We prove that the class of CQT matrices is a Banach algebra with a suitable sub-multiplicative matrix norm $|cdot|$. We introduce a finite representation of CQT matrices together with algorithms which implement elementary matrix operations. An application to solving quadratic matrix equations of the kind $A{X}^2+BX+C=0$, encountered in the solution of Quasi-Birth and Death (QBD) stochastic processes with a denumerable set of phases, is presented where $A,B,C$ are CQT matrices.

Recommendations

• Theoretical and computational properties of semi-infinite quasi-Toeplitz \(M\)-matrices
• On quadratic matrix equations with infinite size coefficients encountered in QBD stochastic processes.
• Quasi-Toeplitz matrix arithmetic: a MATLAB toolbox
• Computing eigenvalues of semi-infinite quasi-Toeplitz matrices
• On the exponential of semi-infinite quasi-Toeplitz matrices

Cites work

• scientific article; zbMATH DE number 3736680 (Why is no real title available?)
• scientific article; zbMATH DE number 1300856 (Why is no real title available?)
• scientific article; zbMATH DE number 1493053 (Why is no real title available?)
• scientific article; zbMATH DE number 3071407 (Why is no real title available?)
• A Fast Direct Solution of Poisson's Equation Using Fourier Analysis
• A unifying approach to some old and new theorems on distribution and clustering
• Computations with infinite Toeplitz matrices and polynomials
• Decay bounds for functions of Hermitian matrices with banded or Kronecker structure
• Decay properties for functions of matrices over \(C^\ast\)-algebras
• Decay rates for quasi-birth-and-death processes with countably many phases and tridiagonal block generators
• Effective fast algorithms for polynomial spectral factorization
• Fast computation of the matrix exponential for a Toeplitz matrix
• GEOMETRIC DECAY OF THE STEADY-STATE PROBABILITIES IN A QUASI-BIRTH-AND-DEATH PROCESS WITH A COUNTABLE NUMBER OF PHASES
• Generalized locally Toeplitz sequences: Spectral analysis and applications to discretized partial differential equations
• Inexact Arnoldi residual estimates and decay properties for functions of non-Hermitian matrices
• Introduction to Matrix Analytic Methods in Stochastic Modeling
• Introduction to large truncated Toeplitz matrices
• Light tail asymptotics in multidimensional reflecting processes for queueing networks
• Networks of Waiting Lines
• Numerical Methods for Structured Markov Chains
• On Direct Methods for Solving Poisson’s Equations
• On functions of quasi-Toeplitz matrices
• On the Effect of Finite Buffer Truncation in a Two-Node Jackson Network
• On the exponential of semi-infinite quasi-Toeplitz matrices
• Product-form characterization for a two-dimensional reflecting random walk
• Revisiting the tail asymptotics of the double QBD process: refinement and complete solutions for the coordinate and diagonal directions
• Spectral Analysis of Nonsymmetric Quasi-Toeplitz matrices with Applications to Preconditioned Multistep Formulas
• Spectral Properties of Banded Toeplitz Matrices
• Spectral properties of the tandem Jackson network, seen as a quasi-birth-and-death process
• The Analyticity of the Roots of a Polynomial as Functions of the Coefficients
• The cyclic reduction algorithm: From Poisson equation to stochastic processes and beyond. In memoriam of Gene H. Golub
• Tri-Layered QBD Processes with Boundary Assistance for Service Resources

Cited in

(15)

• A fast method for solving a block tridiagonal quasi-Toeplitz linear system
• Theoretical and computational properties of semi-infinite quasi-Toeplitz \(M\)-matrices
• On quadratic matrix equations with infinite size coefficients encountered in QBD stochastic processes.
• Quasi-Toeplitz matrix arithmetic: a MATLAB toolbox
• Algorithms for approximating means of semi-infinite quasi-Toeplitz matrices
• A computational framework for two-dimensional random walks with restarts
• Solving quadratic matrix equations arising in random walks in the quarter plane
• Structured perturbation analysis for an infinite size quasi-Toeplitz matrix equation with applications
• The exponential of quasi block-Toeplitz matrices
• Rational Krylov and ADI iteration for infinite size quasi-Toeplitz matrix equations
• Computing eigenvalues of semi-infinite quasi-Toeplitz matrices
• A superharmonic vector for a nonnegative matrix with QBD block structure and its application to a Markov-modulated two-dimensional reflecting process
• New algorithm for solving pentadiagonal CUPL-Toeplitz linear systems
• Fast algorithms for finding the solution of CUPL-Toeplitz linear system from Markov chain
• On the exponential of semi-infinite quasi-Toeplitz matrices

This page was built for publication: Semi-infinite quasi-Toeplitz matrices with applications to QBD stochastic processes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3177717)