An improved FFT-based version of Ramaswami's formula
- 1 January 1997
- journal article
- research article
- Published by Taylor & Francis in Communications in Statistics. Stochastic Models
- Vol. 13 (2) , 223-238
- https://doi.org/10.1080/15326349708807423
Abstract
Ramaswami's formula allows a numerically stable computation of the probability invariant vector of a stochastic matrix ofM/G/1 type. We observe that this formula consists in solving, by means of forward substitution, a block lower triangular block Toeplitz infinite system. By using the natural isomorphism between matrix polynomials and block Toeplitz matrices, we derive a new fast algorithm, based on the use of block FFT's, for the computation of Ramaswami's formula. The proposed algorithm is particularly effective when many block components of the probability invariant vector must be computedKeywords
This publication has 8 references indexed in Scilit:
- On the Solution of a Nonlinear Matrix Equation Arising in Queueing ProblemsSIAM Journal on Matrix Analysis and Applications, 1996
- On the solution of block Hessenberg systemsNumerical Linear Algebra with Applications, 1995
- A logarithmic reduction algorithm for quasi-birth-death processesJournal of Applied Probability, 1993
- Convergence of Spectral Methods for Burgers’ EquationSIAM Journal on Numerical Analysis, 1992
- New results on the single server queue with a batch markovian arrival processCommunications in Statistics. Stochastic Models, 1991
- On ramaswami's algorithm for the computation of the steady state vector in markov chains ofM/G/1-TypeCommunications in Statistics. Stochastic Models, 1990
- A stable recursion for the steady state vector in markov chains of m/g/1 typeCommunications in Statistics. Stochastic Models, 1988
- Polynomial division and its computational complexityJournal of Complexity, 1986