Solving Quadratic Matrix Equations Arising in Random Walks in the Quarter Plane

DOI10.1137/19M1276960zbMATH Open1441.15010arXiv1907.09796OpenAlexW3022771954MaRDI QIDQ5113364FDOQ5113364

Dario A. Bini, B. Meini, Jie Meng

Publication date: 4 June 2020

Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Abstract: Quadratic matrix equations of the kind $A_1{X}^2+A_{0}X+A_{-1}=X$ are encountered in the analysis of Quasi--Birth-Death stochastic processes where the solution of interest is the minimal nonnegative solution $G$. In many queueing models, described by random walks in the quarter plane, the coefficients $A_1,A_0,A_{-1}$ are infinite tridiagonal matrices with an almost Toeplitz structure. Here, we analyze some fixed point iterations, including Newton's iteration, for the computation of $G$ and introduce effective algorithms and acceleration strategies which fully exploit the Toeplitz structure of the matrix coefficients and of the current approximation. Moreover, we provide a structured perturbation analysis for the solution $G$. The results of some numerical experiments which demonstrate the effectiveness of our approach are reported.

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

zbMATH Keywords

fixed point iterationMarkov chainsinfinite matricesrandom walksmatrix equationsToeplitz matricesNewton iteration

Mathematics Subject Classification ID

Toeplitz, Cauchy, and related matrices (15B05) Matrix equations and identities (15A24)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Improved cyclic reduction for solving queueing problems
• Algorithm 432 [C2]: Solution of the matrix equation AX + XB = C [F4]
• Quasi-Toeplitz matrix arithmetic: a MATLAB toolbox
• Introduction to Matrix Analytic Methods in Stochastic Modeling
• Numerical analysis of a quadratic matrix equation
• Numerical Methods for Structured Markov Chains
• Spectral properties of the tandem Jackson network, seen as a quasi-birth-and-death process
• On the Solution of a Nonlinear Matrix Equation Arising in Queueing Problems
• Two Parallel Queues Created by Arrivals with Two Demands I
• 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
• Random Walks in the Quarter Plane
• The stationary tail asymptotics in the GI/G/1-type queue with countably many background states
• GEOMETRIC DECAY OF THE STEADY-STATE PROBABILITIES IN A QUASI-BIRTH-AND-DEATH PROCESS WITH A COUNTABLE NUMBER OF PHASES
• SUFFICIENT CONDITIONS FOR A GEOMETRIC TAIL IN A QBD PROCESS WITH MANY COUNTABLE LEVELS AND PHASES
• Decay rates for quasi-birth-and-death processes with countably many phases and tridiagonal block generators
• On quadratic matrix equations with infinite size coefficients encountered in QBD stochastic processes
• Semi-infinite quasi-Toeplitz matrices with applications to QBD stochastic processes
• Newton's iteration for non-linear equations in Markov chains
• On the Effect of Finite Buffer Truncation in a Two-Node Jackson Network
• Tri-Layered QBD Processes with Boundary Assistance for Service Resources
• Queues with boundary assistance: The effects of truncation
• New convergence results on functional iteration techniques for the numerical solution of M/G/1 type Markov chains
• Truncation and augmentation of level-independent QBD processes.
• A Computational Framework for Two-Dimensional Random Walks With Restarts
• Exact asymptotic formulae of the stationary distribution of a discrete-time two-dimensional QBD process

Cited In (9)

• Theoretical and computational properties of semi-infinite quasi-Toeplitz \(M\)-matrices
• Algorithms for approximating means of semi-infinite quasi-Toeplitz matrices
• Structured perturbation analysis for an infinite size quasi-Toeplitz matrix equation with applications
• Rational Krylov and ADI iteration for infinite size quasi-Toeplitz matrix equations
• Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems
• Computing eigenvalues of semi-infinite quasi-Toeplitz matrices
• A Computational Framework for Two-Dimensional Random Walks With Restarts
• A matrix equation approach to solving recurrence relations in two-dimensional random walks
• Title not available (Why is that?)

Uses Software

• na12
• Algorithm 432
• cqt-toolbox

This page was built for publication: Solving Quadratic Matrix Equations Arising in Random Walks in the Quarter Plane

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