  Quadratic matrix equations of the kind $A_1X^2+A_0X+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.
