Solving certain queueing problems modelled by Toeplitz matrices. (English) Zbl 0813.60094
Summary: By using the concept of generating function associated with a Toeplitz matrix, we analyze existence conditions for the probability invariant vector \(\pi\) of certain stochastic semi-infinite Toeplitz-like matrices. An application to the shortest queue problem is shown. By exploiting the functional formulation given in terms of generating functions, we devise a weakly numerically stable algorithm for computing the probability invariant vector \(\pi\). The algorithm is divided into three stages. At the first stage the zeros of a complex function are numerically computed by means of an extension of the Aberth method. At the second stage the first \(k\) components of \(\pi\) are computed by solving an interpolation problem, where \(k\) is a suitable constant associated with the matrix. Finally, at the third stage a triangular Toeplitz system is solved and its solution is refined by applying the power method or any other refinement method based on regular splittings. In the solution of the triangular Toeplitz system and at each step of the refinement method, special FFT-based techniques are applied in order to keep the arithmetic cost within the \(O(n \log n)\) bound, where \(n\) is an upper bound to the number of the computed components. Numerical comparisons with the available algorithms show the effectiveness of our algorithm in a wide set of cases.
MSC:
| 60K25 | Queueing theory (aspects of probability theory) |
| 90B22 | Queues and service in operations research |
Keywords:
Markov chains; stochastic matrices; queueing problems; stochastic semi- infinite Toeplitz-like matrices; triangular Toeplitz systemReferences:
| [1] | O. Aberth, “Iteration Methods for Finding all Zeros of a Polynomial Simultaneously{”,Math. Comp., 27, (1973), 339–344.} · Zbl 0282.65037 · doi:10.1090/S0025-5718-1973-0329236-7 |
| [2] | L. V. Ahlfors,Complex Analysis. An Introduction to the Theory of Analytic Functions of One Complex Variable, 2nd ed., McGraw-Hill, (1966), New York. · Zbl 0154.31904 |
| [3] | G. S. Ammar, P. Gader, “A Variant of the Gohberg-Semencul Formula Involving Circulant Matrices{”,SIAM J. Matrix Anal. Appl., 12 (1991), 534–541.} · Zbl 0739.65015 · doi:10.1137/0612038 |
| [4] | G. Ammar, P. Gader, “New Decompositions of the Inverse of a Toeplitz Matrix{”,Proc. 1989 Int. Symp. on Math Theory of Networks and Systems (MTNS), (1989), Amsterdam.} · Zbl 0719.65020 |
| [5] | G. S. Ammar, W. G. Gragg, “Superfast Solution of Real Positive Definite Toeplitz Systems{”,SIAM J. Matrix Anal. Appl., 9, (1988), 61–76.} · Zbl 0658.65022 · doi:10.1137/0609005 |
| [6] | D. Bini, V. Pan, “Improved Parallel Computations with Toeplitz-like and Hankel-like Matrices{”,Linear Algebra Appl., 188, (1993), 3–29.} · Zbl 0776.65022 · doi:10.1016/0024-3795(93)90463-X |
| [7] | D. Bini, V. Pan,Matrix and Polynomial Computations, Vol. 1:Fundamental Algorithms, Birkhäuser, Boston, (1994), (to appear). |
| [8] | D. Bini, V. Pan, “Polynomial Division and Its Computational Complexity{”,J. Complexity, 2, (1986), 179–203.} · Zbl 0629.68040 · doi:10.1016/0885-064X(86)90001-4 |
| [9] | J. R. Bunch, “Stability of Methods for Solving Toeplitz Systems of Equations{”,SIAM J. Sci. Statist. Comput., 6, (1985), 349–364.} · Zbl 0569.65019 · doi:10.1137/0906025 |
| [10] | E. Çinlar,Introduction to Stochastic Processes, Prentice-Hall, (1975), New Jersey. · Zbl 0341.60019 |
| [11] | M. Cosnard, P. Fraigniaud, “Asynchronous Durand-Kerner and Aberth Polynomial Root Finding Methods on a Distribuited Memory Multicomputer{”,Proceedings of Parallel Computing, 89, (1989), Leiden.} |
| [12] | P. Delsarte, Y. Genin, “On the Splitting of Classical Algorithms in Linear Prediction Theory{”,IEEE Trans. Acoustics Speech, Signal Process. 35, (1987), 645–653.} · doi:10.1109/TASSP.1987.1165193 |
| [13] | A. M. Dukhovny, “Markov Chains with Quasi Toeplitz Transition Matrix{”,J. Appl. Math. Simulation, 2, (1989), 71–82.} · Zbl 0675.60083 |
| [14] | L. W. Ehrilch, “A Modified Newton Method for Polynomials{”,Comm. A.C.M., 10, (1967), 107–108.} · Zbl 0148.39004 |
| [15] | B. Friedlander, M. Morf, T. Kailath, L. Ljung, “New Inversion Formulas for Matrices Classified in Terms of their Distances from Toeplitz Matrices{”,Linear Algebra Appl., 27, (1979), 31–60.} · Zbl 0414.15005 · doi:10.1016/0024-3795(79)90030-2 |
| [16] | W. Gentleman, G. Sande, “Fast Fourier Transform for Fun and Profit{”,Proc. Fall Joint Comput. Conf., 29, (1966), 563–578.} |
| [17] | G. H. Golub, C. F. Van Loan,Matrix Computations, (1983), Johns Hopkins Univ. Press, Baltimore, Maryland. · Zbl 0559.65011 |
| [18] | F. G. Gustavson, D. Y. Y. Yun, “Fast Algorithms for Rational Hermite Approximation and Solution of Toeplitz Systems{”,IEEE Trans. Circuits and Systems, 26, (1979), 750–755.} · Zbl 0416.65008 · doi:10.1109/TCS.1979.1084696 |
| [19] | G. Heining, K. Rost,Algebraic Methods for Toeplitz-like Matrices and Operators, Operator Theory, 13, Birkhäuser, 1984. |
| [20] | D. P. Heyman, “Approximating the Stationary Distribution of an Infinite Stochastic Matrix{”,J. Appl. Prob., 28, (1991), 96–103.} · Zbl 0721.60070 · doi:10.2307/3214743 |
| [21] | P. Henrici,Applied and Computational Complex Analysis, Vol. 1:Power Series, Integration, Conformal Mapping, Location of Zeros, John Wiley and Sons, New York, 1974. · Zbl 0313.30001 |
| [22] | I. S. Iohvidov,Hankel and Toeplitz Matrices and Forms, Algebraic Theory, Birkhäuser, Boston, 1982. · Zbl 0493.15018 |
| [23] | T. Kailath, “Signal Processing Applications of Some Moment Problems{”,Proc. AMS Symp. in Applied Math., 37, (1987), 71–100.} · Zbl 0644.94005 |
| [24] | T. Kailath, A. Viera, M. Morf, “Inverses of Toeplitz Operators, Innovations, and Orthogonal Polynomials{”,SIAM Rev., 20, (1978), 106–119.} · Zbl 0382.47013 · doi:10.1137/1020006 |
| [25] | L. Kaufman, “Matrix Methods for Queueing Problems{”,SIAM J. Sci. Stat. Comput., 4, (1983), 525–552.} · Zbl 0551.65096 · doi:10.1137/0904037 |
| [26] | G. Labahn, Dong Koo Choi, S. Cabay, “The Inverses of Block Hankel and Block Toeplitz Matrices{”,SIAM J. Comput., 19, (1990), 98–123.} · Zbl 0716.15003 · doi:10.1137/0219006 |
| [27] | E. Linzer, “On the Stability of Transform-Based Circular Deconvolution{”,SIAM J. Numer. Anal., 29, (1992), 1482–1492.} · Zbl 0761.65014 · doi:10.1137/0729085 |
| [28] | M. F. Neuts, “Queues Solvable without Rouché’s Theorem{”,Oper. Res., 27, (1979), 767–781.} · Zbl 0434.60094 · doi:10.1287/opre.27.4.767 |
| [29] | M. F. Neuts,Structured Stochastic Matrices of M/G/1 Type and their Applications, Dekker, (1981), New York. |
| [30] | D. J. Rose, “Convergent Regular Splitting for Singular M-Matrices{”,SIAM J. Alg. Disc. Meth., (1984), 133–144.} |
| [31] | E. Seneta, “Computing the Stationary Distribution for Infinite Markov Chains{”,Linear Algebra Appl., 34, (1980), 259–267.} · Zbl 0484.65086 · doi:10.1016/0024-3795(80)90168-8 |
| [32] | P. Weidner, “The Durand-Kerner Method for Trigonometric and Exponential Polynomials{”,Computing, 40, (1988), 175–179.} · Zbl 0631.65045 · doi:10.1007/BF02247945 |
| [33] | W. Werner, “On the Simultaneous Determination of Polynomial Roots{”,Lectures Notes in Mathematics, 953, Springer Berlin, (1982), 188–202.} · Zbl 0504.65024 · doi:10.1007/BFb0069383 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
