Fast solvers for queueing systems with negative customers

ABSTRACT

In this paper, we are interested in solving queueing systems having Poisson batch arrivals, exponential servers and negative customers. Preconditioned Conjugate Gradient (PCG) method is applied to solving the steady-state probability distribution of the queueing system. Preconditioners are constructed by exploiting near-Toeplitz structure of the generator matrix and the Gohberg-Semumcul formula. We proved that the preconditioned system has singular values clustered around one. Therefore Conjugate Gradient (CG) methods when applied to solving the preconditioned system, we expect fast convergence rate. Numerical examples are given to demonstrate our claim.

REFERENCES

• 1: A. Ben-Artzi and T. Shalom, On Inversion of Toeplitz and Close to Toeplitz Matrices, Linear Algebra Appl., 75 (1986) 173--192.
• 2: R. Chan, D. Potts and G. Steidl, Preconditioners for non-Hermitian Toeplitz systems, Numerical Linear Algebra with Applications, 8(2001)83--98.
• 3: W. Ching, Iterative Methods for Queueing Systems with Batch Arrivals and Negative Customers, BIT, 43 (2003) 285--296.
• 4: Wai-KI Ching , Michael K. Ng , W. Ching, Markov Chains: Models, Algorithms and Applications (International Series in Operations Research & Management Science), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 5: E. Gelenbe, Random Neural Networks with Positive and Negative Signals and Product Solution, Neural Computation. 1 (1989), pp. 501--510.
• 6: P. Glynn, and K. Sigman, Queues with Negative Arrivals, J. Appl. Prob. 28 (1991), pp. 245--250.
• 7: E. Gelenbe, Product Form Networks with Negative and Positive Customers, J. Appl. Prob. 28 (1991), pp. 656--663.
• 8: I. Gohberg and A. Semencul, On the Inversion of Finite Toeplitz Matrices and Their Continuous Analogs, Mat. Issled., 2 (1972) 201--233.
• 9: P. Harrison, Reliability modeling Using G-queue, Euro. J. Oper. Res. 126 (2000), pp. 273--387.
• 10: G. Heinig, On the Reconstruction of Toeplitz Matrix Inverses from Columns, Linear Algebra Appl., 350 (2002) 199--212.
• 11: S. Jaffard, Propriétés des matrices "bien localisées" près de leur diagonale et quelques applications, Ann. Inst. H. Poincaré Anal. Non Linéaire, 7 (1990) 461--476.
• 12: G. Labahn and T. Shalom, Inversion of Toeplitz Matrices with only Two Standard Equations, Linear Algebra Appl., 175 (1992) 143--158.
• 13: F. Lin and W. Ching, Inverse Toeplitz preconditioners for Hermitian Toeplitz systems, Numerical Linear Algebra with Applications, 12(2005)221--229.
• 14: T. Strohmer, Four Short Stories about Toeplitz Matrix Calculations, Linear Algebra Appl., 343--344 (2002) 321--344.
• 15: M. Ng, K. Rost and Y. Wen, On Inversion of Toeplitz Matrices, Linear Algebra Appl., 348 (2002) 145--151.
• 16: R. Varga, Matrix Iterative Analysis, Prentice-Hall, New Jersey, 1963.
• 17: Y. Wen, M. Ng, W. Ching and H. Liu, A note on the Stability of Toeplitz Matrix Inversion Formulas, Appl. Math. Letters 17 (2004) 903--907.
• 18: Y. Wen, W. Ching and M. Ng, Approximate Inverse-Free Preconditioners for Toeplitz Matrices, submitted.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Queueing theory

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Unbounded-action devices (e.g., cellular automata, circuits, networks of machines)

General Terms:
Theory

Keywords:
Gohberg-Semencul formula, negative customer, preconditioned conjugate gradient method, preconditioners, queueing systems