Volume 17, pp. 151-167, 2004.

A quadratically convergent Bernoulli-like algorithm for solving matrix polynomial equations in Markov chains

C. He, B. Meini, N. H. Rhee, and K. Sohraby


A quadratically convergent algorithm is developed for solving matrix polynomial equations arising in M/G/1 and G/M/1 type Markov chains. The algorithm is based on the computation of generalized block eigenvalues/vectors of a suitable pair of matrices by means of a Bernoulli-like method. The use of the displacement structure allows one to reduce the computational cost per step. A shifting technique speeds up the rate of convergence.

Full Text (PDF) [199 KB], BibTeX

Key words

polynomial matrix equations, Markov chains, generalized eigenvalues/eigenvectors, displacement structure.

AMS subject classifications

15A24, 60J22, 65F15.

< Back