Abstract. Recently, it has been proved by V. Ramaswami that an M/G/1 type Markov chain can be rewritten in terms of a suitable QBD process, with infinite and strongly structured block entries \cite{ram:mam2}. This reformulation allows to derive new algorithms for the computation of the matrix $G$. We show that by applying the cyclic reduction algorithm to the QBD process we generate a sequence of QBDs, having constant displacement rank. More precisely, we show that these blocks belong to the algebra generated by a suitable block Frobenius matrix. This fact allows us to devise a new quadratically convergent algorithm, that makes use of Fast Fourier Transforms and of Toeplitz matrix computations, for approximating the matrix $G$. A complexity analysis is performed.

 <dvi>  <postscript>  files of the paper