On the numerical solution of a nonlinear matrix equation in Markov chains (Q1300874)

The author considers the matrix equation \[ G= \sum^\infty_{i= 0} A_iG^i,\tag{1} \] where \(G\in\mathbb{R}^{m\times m}\) is an unknown matrix and \((A_i)_i\) is a family of elementwise nonnegative \(m\times m\) matrices such that \(\sum^\infty_{i= 0} A_i\) is a stochastic matrix, i.e. \(Ae= e\) where \(e\) is the column vector with all components equal to one. Equation (1) is important in the study of Markov chains that arise in a variety of queueing problems. It is known that (1) has at least one nonnegative solution for which \(Ge\leq e\). The desired solution is the minimal nonnegative solution. The author mentions three different fixed point iteration methods to solve (1). He then proposes a new inversion-free algorithm which is particularly useful on a parallel computing system. He proves convergence results for the new algorithm, shows that its convergence rate is competitive with the fastest of the three original algorithms and provides numerical tests.