High accuracy algorithms for High accuracy algorithms for numerical solutions of queueing problems

Qiang Ye

Department of Mathematics, University of Manitoba, Winnipeg, Manitoba, Canada R3T 2N2 (ye@cc.UManitoba.CA)

Abstract

In this talk, we shall discuss recent advances in entrywise perturbation theory and high accuracy algorithms for diagonally dominant M-matrices and present their applications to high accuracy computations in solving queuing problems. Diagonally dominant M-matrices arise in a large variety of applications, including the queuing models. In the recent works [1,2], we have shown that, if each off-diagonal entry and the diagonally dominant part of a diagonally dominant M-matrix is determined to high relative accuracy, then its smallest eigenvalue (corresponding to the Perron root of the inverse) and each entry of its inverse are all determined to the same relative accuracy. New algorithms have also been developed that compute these quantities with relative errors in the magnitude of the machine precision. These more accurate algorithms can be used, for example, to compute h to high accuracy where h is the decay rate for queue length in GI/M/1 queuing systems. Note that the quantity delta = 1-h is also of interest in such applications and hence high accuracy h is necessary when h is close to 1.

Here, we shall consider functional iteration algorithms for solving nonlinear matrix equations arising in queuing models. Specifically, to solve

G = Sk = 0¥ Ak Gk
of M/G/1 type queues, each step of functional iterations typically involves solving a linear system such as Gi+1 = (I-Sk = 1¥ Ak Gik-1)-1 A0 . Using the traditional algorithms for linear systems will lead to a backward stable solution and thus the accuracy in G is normwise only (i.e. smaller entries of G may have larger relative errors) and depends on a condition number. However, noting that I-Sk = 1¥ AkGik-1 is a diagonally dominant M-matrix, we can use the new algorithm to obtain a componentwise accurate solution which is also independent of any condition number. Rounding error analysis and numerical examples will be presented to illustrate the effectiveness of the new approach.

References

[1]
S.Alfa, J.Xue and Q.Ye, Entrywise perturbation theory for diagonally dominant M-matrices with applications, submitted

[2]
S.Alfa, J.Xue and Q.Ye, Accurate computation of the smallest eigenvalue of a diagonally dominant M-matrix, submitted


File translated from TEX by TTH, version 1.94.
On 5 May 1999, 11:00.