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...

This publication has 11 references indexed in Scilit: