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

DOI10.1090/MCOM/3301zbMATH Open1393.15038arXiv1611.06337OpenAlexW2554229472MaRDI QIDQ3177717FDOQ3177717

Dario A. Bini, Stefano Massei, B. Meini

Publication date: 1 August 2018

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

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.

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

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

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)

Cites Work

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

Cited In (14)

• A fast method for solving a block tridiagonal quasi-Toeplitz linear system
• Theoretical and computational properties of semi-infinite quasi-Toeplitz \(M\)-matrices
• Solving Quadratic Matrix Equations Arising in Random Walks in the Quarter Plane
• Quasi-Toeplitz matrix arithmetic: a MATLAB toolbox
• Algorithms for approximating means of semi-infinite quasi-Toeplitz matrices
• 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 Computational Framework for Two-Dimensional Random Walks With Restarts
• 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)