Abstract. The cyclic reduction technique \cite{rc}, rephrased in functional form \cite{bm2}, pro\-vides a numerically stable, quadratically convergent method, for solving the matrix equation $X=\sum_{i=0}^{+\infty}X^iA_i$, where the $A_i$'s are nonnegative $k\times k$ matrices such that $\sum_{i=0}^{+\infty}A_i$ is column stochastic. In this paper we propose a further improvement of the above method, based on a point-wise evaluation/interpolation at a suitable set of Fourier points, of the functional relations defining each step of cyclic reduction \cite{bm2}. This new technique allows us to devise an algorithm based on FFT having a lower computational cost and a higher numerical stability. Numerical results and comparisons are provided.

  <dvi>  <postscript>  files of the paper