Abstract. By extending the cyclic reduction technique to infinite block matrices we devise a new algorithm for computing the solution $G_0$ of the matrix equation $G=\sum_{i=0}^{+\infty}G^iA_i$ arising in a wide class of queueing problems. Here $A_i$, $i=0,1,\ldots,$ are $k\times k$ nonnegative matrices such that $\sum_{i=0}^{+\infty}A_i$ is column-stochastic. Our algorithm, which under mild conditions generates a sequence of matrices converging quadratically to $G_0$, can be fully described in terms of simple operations between matrix power series, i.e., power series in $z$ having matrix coefficients. Such operations, like multiplication and reciprocation modulo $z^m$, can be quickly computed by means of FFT-based fast polynomial arithmetic; here $m$ is the degree where the power series are numerically cut off in order to reduce them to polynomials. These facts lead to a dramatic reduction of the complexity of solving the given matrix equation, in fact, $O(k^3m+k^2 m \log m)$ arithmetic operations are sufficient to carry out each iteration of the algorithm. Numerical experiments and comparisons performed with the customary techniques, show the effectiveness of our algorithm. For a problem arising from the modelling of metropolitan networks, our algorithm resulted to be about 30 times faster than the algorithms customarily used in the applications. Cyclic reduction applied to QBD problems leads to an algorithm similar to the one of [11] but having a lower computational cost.

<postscript>  files of the paper