Abstract. Ramaswami's formula allows a numerically stable computation of the probability invariant vector of a stochastic matrix of $M/G/1$ type. We observe that this formula consists in solving, by means of forward substitution, a block lower triangular block Toeplitz infinite system. By using the natural isomorphism between matrix polynomials and block Toeplitz matrices, we derive a new fast algorithm, based on the use of block FFT's, for the computation of Ramaswami's formula. The proposed algorithm is particularly effective when many block components of the probability invariant vector must be computed.

<dvi>  <postscript>   files of the paper