On the Solution of a Nonlinear Matrix Equation Arising in Queueing Problems
Authors:
- Dario BiniDBDario Bini
- Beatrice MeiniBMBeatrice Meini
- 1 October 1996
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Matrix Analysis and Applications
- Vol. 17 (4) , 906-926
Abstract
By extending the cyclic reduction technique to infinite block matrices we devise a new algorithm for computing the solution $G_0 $ of the matrix equation $G = \Sigma _{i = 0}^{ + \infty } G^i A_i $ arising in a wide class of queueing problems. Here $A_i ,i = 0,1, \cdots ,$ are $k \times k$ nonnegative matrices such that $\Sigma _{i = 0}^{ + \infty } A_i $ is column stochastic. Our algorithm, which under mild conditions generates a sequence of matrices converging quadratically to $G_0 $, can be fully described in terms of simple operations between matrix power series, i.e., power series in z having matrix coefficients. Such operations, like multiplication and reciprocation modulo $z^m $, can be quickly computed by means of FFT-based fast polynomial arithmetic; here m is the degree where the power series are numerically cut off in order to reduce them to polynomials. These facts lead to a dramatic reduction of the complexity of solving the given matrix equation; in fact, $O( k^3 m + k^2 m \log m )$ arithmet...
Keywords
This publication has 11 references indexed in Scilit:
- New convergence results on functional iteration techniques for the numerical solution of M/G/1 type Markov chainsNumerische Mathematik, 1997
- On Cyclic Reduction Applied to a Class of Toeplitz-Like Matrices Arising in Queueing Problems1995
- Newton's iteration for non-linear equations in Markov chainsIMA Journal of Numerical Analysis, 1994
- Polynomial and Matrix Computations1994
- A logarithmic reduction algorithm for quasi-birth-death processesJournal of Applied Probability, 1993
- On the Stability of Transform-Based Circular DeconvolutionSIAM Journal on Numerical Analysis, 1992
- Nonlinear Matrix Equations in Applied Probability—Solution Techniques and Open ProblemsSIAM Review, 1988
- Polynomial division and its computational complexityJournal of Complexity, 1986
- Regenerative Analysis and Steady State Distributions for Markov ChainsOperations Research, 1985
- On Direct Methods for Solving Poisson’s EquationsSIAM Journal on Numerical Analysis, 1970