Abstract. A survey on numerical methods, based on Toeplitz matrix computation, for the solution of M/G/1 type Markov chains is presented together with some new advances. We show how the block Toeplitz structure, shared by the transition matrices associated with M/G/1 type Markov chains, can be exploited as the basis for devising fast and numerically stable algorithms, for the computation of the probability invariant vector and for the solution of the nonlinear matrix equation $X=\sum_{i=0}^{+\infty}A_iX^i$.

 <dvi>  <postscript>  files of the paper