swMATH ID: 11490
Software Authors: Bini, Dario Andrea; Meini, Beatrice
Description: 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 = ∑+ ∞ i=0 Xi Ai, where the Ai’s are nonnegative k × k matrices such that ∑+ ∞ i=0 Ai 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.
Homepage: http://www.netlib.org/numeralgo/index.html
Dependencies: Netlib
Keywords: queueing problems; \(M/G/1\) type matrices; Toeplitz matrices; numerical examples; cyclic reduction; matrix equation; numerical stability
Related Software: SMCSolver; Matlab; cqt-toolbox; Algorithm 432; SQUINT; na10; na31; mftoolbox; OPQ; FISHPAK; mctoolbox; FFTW; SLICOT; TELPACK
Cited in: 29 Publications

Citations by Year