Improved cyclic reduction for solving queueing problems

The cyclic reduction technique (Buzbee et al., 1970), rephrased in functional form (Bini and Meini, 1996), provides a numerically stable, quadratically convergent method for solving the matrix equation X = Sigma(i=0)(+infinity) X(i)A(i), where the A(i)'s are nonnegative k x k matrices such that Sigma(i=0)(+infinity) 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 (Bini and Meini, 1996). 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.