Abstract. We propose a new quadratically convergent algorithm for solving Non-Skip-Free M/G/1 type Markov chains. This algorithm consists in applying the cyclic reduction technique of \cite{bm:gcr}, \cite{bm:pwcr} to the reblocked M/G/1 type Markov chain and in exploiting the Toeplitz structure by means of the concept of displacement rank. The complexity of our algorithm, applied to a Markov chain with $k$ boundary levels and with the number of phases equal to $p$, is $O(np^3k\log^2 k+p^2 k n\log (kn))$ arithmetic operations, where $n$ is the numerical truncation level of the power series involved. This complexity bound is better than the $O(m^3 n+m^2n\log n)$ bound of the cyclic reduction applied to the reblocked matrix without using the inner structure of the problem, where $m=kp$. Structural properties of the corresponding $G$ matrix are proved in terms of displacement operators. For QBD problems the cost is reduced to $O(p^3k\log^2 k)$ operations, moreover, convergence results are proved in terms of the location of the zeros of a suitable polynomial associated with the Markov chain. Numerical results are presented.

  <dvi>  <postscript>  files of the paper