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

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.