Improved cyclic reduction for solving queueing problems
type: Item
instance of: scholarly article
title: Improved cyclic reduction for solving queueing problems
zbMATH Open document ID: 0887.65144
DOI: 10.1023/A:1019206402431
author: Dario A. Bini
author: B. Meini
published in: Numerical Algorithms
publication date: 1997-10-26T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 65C99
Mathematics Subject Classification ID: 60K25
zbMATH DE Number: 1078350
zbMATH Keywords: queueing problems
zbMATH Keywords: \(M/G/1\) type matrices
zbMATH Keywords: Toeplitz matrices
zbMATH Keywords: numerical examples
zbMATH Keywords: cyclic reduction
zbMATH Keywords: matrix equation
zbMATH Keywords: numerical stability
reviewed by: George S. Stavrakakis
MaRDI profile type: Publication
full work available at URL: a:1019206402431
OpenAlex ID: W1659699428
description: scientific article; zbMATH DE number 1078350