Opsearch

In the matrix-analytic, algorithmic solution of a number of queueing models involving phase type distributions, the central item to compute is the entrywise minimal nonegative solution of a non-linear matrix equation of the form R = σRnAn or .G = σAnGn The matrices A n are obtained as the integral with respect to a distribution function of a set of m,atrices p(n,t) which satisfy an infinite system of differential difference equations. Examples of such models are the special cases of the GI/G/1 queue such as GI/PH/1 and PH/G/1, which respectively correspond to the GI/G/1 queue where the service time or interarrival time are phase tupe random variables. In this paper, we devise an efficient scheme to compute the solution of these non-linear matrix equations without computing and storing the matrices P(n,t) or the matrix sequence An. The algorithm presented requires a small number o matrices to be stored, yields a stable recursive scheme involving only nonegative matrices, and is seen to perform wellover a wide range of examples we have tested. The results here constitute a set of major simplifications in the algorithmic approach to these models and extend the realm of inplementability of the matrix analytic techniques even for problems of large dimensionality. The analysis presented here carries over to the multi-server queue with phase type servers.