Affiliation: | a Dipartimento di Matematica “L. Tonelli”, Università di Pisa, via Buonarroti 2, 56127 Pisa, Italy b Département d'Informatique, U.L.B., C.P. 212, Boulevard du Triomphe 1050, Bruxelles, Belgium |
Abstract: | The matrix equation ∑i=0nAiXi=0, where the Ai's are m×m matrices, is encountered in the numerical solution of Markov chains which model queueing problems. We provide here a unifying framework in terms of Möbius' mapping to relate different resolution algorithms having a quadratic convergence. This allows us to compare algorithms like logarithmic reduction (LR) and cyclic reduction (CR), which extend Graeffe's iteration to matrix polynomials, and the invariant subspace (IS) approach, which extends Cardinal's algorithm. We devise new iterative techniques having quadratic convergence and present numerical experiments. |