D. Bini et B. Meini, ON THE SOLUTION OF A NONLINEAR MATRIX EQUATION ARISING IN QUEUING-PROBLEMS, SIAM journal on matrix analysis and applications, 17(4), 1996, pp. 906-926
By extending the cyclic reduction technique to infinite block matrices
we devise a new algorithm for computing the solution G(0) of the matr
ix equation G = Sigma(i=0)(+infinity) G(i) A(i) arising in a wide clas
s of queueing problems. Here A(i), i = 0, 1,..., are k x k nonnegative
matrices such that Sigma(i=0)(+infinity) A(i) is column stochastic. O
ur algorithm, which under mild conditions generates a sequence of matr
ices 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 module z(m), can be quickly computed by means of FFT
-based fast polynomial arithmetic; here m is the degree where the powe
r series are numerically cut off in order to reduce them to polynomial
s. These facts lead to a dramatic reduction of the complexity of solvi
ng the given matrix equation; in fact, O(k(3)m + k(2)m log m) arithmet
ic operations are sufficient to carry out each iteration of the algori
thm. Numerical experiments and comparisons performed with the customar
y techniques show the effectiveness of our algorithm. For a problem ar
ising from the modelling of metropolitan networks, our algorithm was a
bout 30 times faster than the algorithms customarily used in the appli
cations. Cyclic reduction applied to quasi-birth-death (QBD) problems,
i.e., problems where A(i) = O for i > 2, leads to an algorithm simila
r to the one of [Latouche and Ramaswami, J. Appl. Probab., 30 (1993),
pp. 650-674], but which has a lower computational cost.