Solving quadratic matrix equations arising in random walks in the quarter plane

DOI10.1137/19M1276960MaRDI QIDQ5113364zbMATH OpenOpenAlexFDO

Authors 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)

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)

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.

Recommendations

• On quadratic matrix equations with infinite size coefficients encountered in QBD stochastic processes.
• Numerical analysis of a quadratic matrix equation
• scientific article; zbMATH DE number 1974610
• Highly accurate Latouche-Ramaswami logarithmic reduction algorithm for quasi-birth-and-death process
• Newton-Shamanskii method for a quadratic matrix equation arising in quasi-birth-death problems

Cites work

• scientific article; zbMATH DE number 3736680 (Why is no real title available?)
• scientific article; zbMATH DE number 193017 (Why is no real title available?)
• A computational framework for two-dimensional random walks with restarts
• Algorithm 432 [C2]: Solution of the matrix equation AX + XB = C [F4]
• Decay rates for quasi-birth-and-death processes with countably many phases and tridiagonal block generators
• Exact asymptotic formulae of the stationary distribution of a discrete-time two-dimensional QBD process
• GEOMETRIC DECAY OF THE STEADY-STATE PROBABILITIES IN A QUASI-BIRTH-AND-DEATH PROCESS WITH A COUNTABLE NUMBER OF PHASES
• Improved cyclic reduction for solving queueing problems
• Introduction to Matrix Analytic Methods in Stochastic Modeling
• Light tail asymptotics in multidimensional reflecting processes for queueing networks
• New convergence results on functional iteration techniques for the numerical solution of M/G/1 type Markov chains
• Newton's iteration for non-linear equations in Markov chains
• Numerical Methods for Structured Markov Chains
• Numerical analysis of a quadratic matrix equation
• On quadratic matrix equations with infinite size coefficients encountered in QBD stochastic processes.
• On the Effect of Finite Buffer Truncation in a Two-Node Jackson Network
• On the Solution of a Nonlinear Matrix Equation Arising in Queueing Problems
• Quasi-Toeplitz matrix arithmetic: a MATLAB toolbox
• Queues with boundary assistance: The effects of truncation
• Random walks in the quarter plane. Algebraic methods, boundary value problems, applications to queueing systems and analytic combinatorics
• Revisiting the tail asymptotics of the double QBD process: refinement and complete solutions for the coordinate and diagonal directions
• SUFFICIENT CONDITIONS FOR A GEOMETRIC TAIL IN A QBD PROCESS WITH MANY COUNTABLE LEVELS AND PHASES
• Semi-infinite quasi-Toeplitz matrices with applications to QBD stochastic processes
• Spectral properties of the tandem Jackson network, seen as a quasi-birth-and-death process
• The stationary tail asymptotics in the GI/G/1-type queue with countably many background states
• Tri-Layered QBD Processes with Boundary Assistance for Service Resources
• Truncation and augmentation of level-independent QBD processes.
• Two Parallel Queues Created by Arrivals with Two Demands I

Cited in

(11)

• On quadratic matrix equations with infinite size coefficients encountered in QBD stochastic processes.
• Structured perturbation analysis for an infinite size quasi-Toeplitz matrix equation with applications
• Algorithms for approximating means of semi-infinite quasi-Toeplitz matrices
• A computational framework for two-dimensional random walks with restarts
• Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems
• Theoretical and computational properties of semi-infinite quasi-Toeplitz \(M\)-matrices
• A matrix equation approach to solving recurrence relations in two-dimensional random walks
• Rational Krylov and ADI iteration for infinite size quasi-Toeplitz matrix equations
• Solving quadratic matrix equations and factoring polynomials: new fixed point iterations based on Schur complements of Toeplitz matrices
• Computing eigenvalues of semi-infinite quasi-Toeplitz matrices
• scientific article; zbMATH DE number 1974610 (Why is no real title available?)

Describes a project that uses

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)