Improved cyclic reduction for solving queueing problems (Q1370339)

The cyclic reduction technique, rephrased in functional form, provides a numerically convergent method for solving the matrix equation \(X= \sum^{+\infty}_{i=0} X^i A_i\), where the \(A_i\)'s are nonnegative \(k\times k\) matrices such that \(\sum^{+\infty}_{i=0} A_i\), is column stochastic. In this paper a further improvement of the above method is proposed, based on a pointwise evaluation/interpolation at a suitable set of Fourier points, of the functional relations defining each step of cyclic reduction. This new technique allows to devise an algorithm based on the fast Fourier transform having a lower computational cost and a higher numerical stability. Numerical results and comparisons are provided.