×

Componentwise accurate fluid queue computations using doubling algorithms. (English) Zbl 1326.65055

This article develops algorithms for two-dimensional Markov-modulated queues \(\{ X(t),\phi(t)\}\) that model many real-life applications. To find the stationary distribution of Markov-modulated fluid queues is equivalent to finding the minimal nonnegative solution to a Riccati equation of the form \( B - AX - XD + XCX = 0\). In this context, \(M = \left( \begin{smallmatrix} D & -C\\ -B & A \end{smallmatrix} \right)\) is a singular \(M\)-matrix of special type. To solve this problem the authors suggest a structured doubling algorithm (SDA), see [X.-X. Guo et al., Numer. Math. 103, No. 3, 393–412 (2006; Zbl 1097.65055)], and its variants, see [D. A. Bini et al., Numer. Math. 116, No. 4, 553–578 (2010; Zbl 1202.15016)] or [W.-G. Wang et al., SIAM J. Matrix Anal. Appl. 33, No. 1, 170–194 (2012; Zbl 1258.65045)], and compute componentwise accurate solutions, see [J. Xue et al., Numer. Math. 120, No. 4, 639–670 (2012; Zbl 1245.65053)], in its GTH-like linear equations solver for nonsingular \(M\)-matrices. This is intended to give accurate results for problems with badly scaled solutions and results in a componentwise accurate SDA method.

MSC:

65F30 Other matrix algorithms (MSC2010)
65F05 Direct numerical methods for linear systems and matrix inversion
65C50 Other computational problems in probability (MSC2010)
60K25 Queueing theory (aspects of probability theory)
15A24 Matrix equations and identities
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alfa, A.S., Xue, J., Ye, Q.: Accurate computation of the smallest eigenvalue of a diagonally dominant \[M\] M-matrix. Math. Comput. 71(237), 217-236 (2002) · Zbl 0984.65033 · doi:10.1090/S0025-5718-01-01325-4
[2] Arioli, M., Codenotti, B., Fassino, C.: The Padé method for computing the matrix exponential. Linear Algebra Appl. 240, 111-130 (1996) · Zbl 0851.65024 · doi:10.1016/0024-3795(94)00190-1
[3] Bean, N.G., O’Reilly, M.M., Sargison, J.E.: A stochastic fluid flow model of the operation and maintenance of power generation systems. IEEE Trans. Power Syst. 25(3), 1361-1374 (2010) · Zbl 1193.74014 · doi:10.1109/TPWRS.2010.2042308
[4] Berman, A., Plemmons, R.J.: Nonnegative matrices in the mathematical sciences, Classics in Applied Mathematics, vol. 9. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (1994, revised reprint of the 1979 original) · Zbl 0484.15016
[5] Bini, D.A., Gemignani, L.: Solving quadratic matrix equations and factoring polynomials: new fixed point iterations based on Schur complements of Toeplitz matrices. Numer. Linear Algebra Appl. 12(2-3), 181-189 (2005) · Zbl 1164.65379 · doi:10.1002/nla.410
[6] Bini, D.A., Iannazzo, B., Meini, B.: Numerical solution of algebraic Riccati equations, Fundamentals of Algorithms, vol. 9. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (2012) · Zbl 1244.65058
[7] Bini, D.A., Iannazzo, B., Meini, B., Poloni, F.: Nonsymmetric algebraic Riccati equations associated with an M-matrix: recent advances and algorithms. In: Olshevsky, V., Tyrtyshnikov, E. (eds.) Matrix Methods: Theory, Algorithms and Applications, chapter 10, pp. 176-209. World Scientific Publishing (2010) · Zbl 1215.65077
[8] Bini, D.A., Latouche, G., Meini, B.: Numerical Methods for Structured Markov Chains. Numerical Mathematics and Scientific Computation. Oxford University Press, Oxford (2005) · Zbl 1076.60002 · doi:10.1093/acprof:oso/9780198527688.001.0001
[9] Bini, D.A., Meini, B., Poloni, F.: Transforming algebraic Riccati equations into unilateral quadratic matrix equations. Numer. Math. 116(4), 553-578 (2010) · Zbl 1202.15016 · doi:10.1007/s00211-010-0319-2
[10] Crabtree, D.E., Haynsworth, E.V.: An identity for the Schur complement of a matrix. Proc. Am. Math. Soc. 22, 364-366 (1969) · Zbl 0186.34003 · doi:10.1090/S0002-9939-1969-0255573-1
[11] da Silva Soares, A.: Fluid queues—building upon the analogy with QBD processes. PhD thesis, Université libre de Bruxelles (2005) · Zbl 1202.15016
[12] Golub, G.H., Van Loan, C.F.: Matrix Computations. Johns Hopkins Studies in the Mathematical Sciences, 3rd edn. Johns Hopkins University Press, Baltimore (1996)
[13] Govorun, M., Latouche, G., Remiche, M.-A.: Stability for fluid queues: characteristic inequalities. Stoch. Models 29(1), 64-88 (2013) · Zbl 1271.60097 · doi:10.1080/15326349.2013.750533
[14] Guo, X.-X., Lin, W.-W., Xu, S.-F.: A structure-preserving doubling algorithm for nonsymmetric algebraic Riccati equation. Numer. Math. 103, 393-412 (2006) · Zbl 1097.65055 · doi:10.1007/s00211-005-0673-7
[15] Higham, N.J.: The Matrix Function Toolbox. http://www.ma.man.ac.uk/higham/mftoolbox
[16] Higham, N.J.: Accuracy and Stability of Numerical Algorithms, 2nd edn. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (2002) · Zbl 1011.65010 · doi:10.1137/1.9780898718027
[17] Higham, N.J.: The scaling and squaring method for the matrix exponential revisited. SIAM J. Matrix Anal. Appl. 26(4), 1179-1193 (2005, electronic) · Zbl 1081.65037
[18] Higham, N.J.: Functions of Matrices. Theory and Computation. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (2008) · Zbl 1167.15001
[19] Latouche, G., Taylor, P.G.: A stochastic fluid model for an ad hoc mobile network. Queueing Syst. 63(1), 109-129 (2009) · Zbl 1193.90055 · doi:10.1007/s11134-009-9153-6
[20] Mandjes, M., Mitra, D., Scheinhardt, W.: Simple models of network access, with applications to the design of joint rate and admission control. In: INFOCOM 2002. Proceedings of Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies. IEEE, vol. 1, pp. 3-12 (2002) · Zbl 1035.68010
[21] Meyer, C.D.: Stochastic complementation, uncoupling Markov chains, and the theory of nearly reducible systems. SIAM Rev. 31(2), 240-272 (1989) · Zbl 0685.65129 · doi:10.1137/1031050
[22] Mitra, D.: Stochastic theory of a fluid model of producers and consumers coupled by a buffer. Adv. Appl. Probab. 20(3), 646-676 (1988) · Zbl 0656.60079 · doi:10.2307/1427040
[23] Poloni, F., Reis, T.: The SDA method for numerical solution of Lur’e equations. Technical Report 1101.1231, arXiv.org (2011) · Zbl 0984.65033
[24] Ramaswami, V.; Smith, D. (ed.); Hey, P. (ed.), Matrix analytic methods for stochastic fluid flows, 1019-1030 (1999), Edinburgh · Zbl 0978.60092
[25] Rogers, L.C.G.: Fluid models in queueing theory and Wiener-Hopf factorization of Markov chains. Ann. Appl. Probab. 4, 390-413 (1994) · Zbl 0806.60052 · doi:10.1214/aoap/1177005065
[26] Shao, M., Gao, W., Xue, J.: Aggressively truncated Taylor series method for accurate computation of exponentials of essentially nonnegative matrices. SIAM J. Matrix Anal. Appl. 35(2), 317-338 (2014) · Zbl 1309.65051 · doi:10.1137/120894294
[27] van Foreest, N., Mandjes, M., Scheinhardt, W.: Analysis of a feedback fluid model for heterogeneous TCP sources. Stoch. Models 19(3), 299-324 (2003) · Zbl 1024.60040 · doi:10.1081/STM-120023563
[28] Wang, W.-G., Wang, W.-C., Li, R.-C.: Alternating-directional doubling algorithm for \[M\] M-matrix algebraic Riccati equations. SIAM J. Matrix Anal. Appl. 33(1), 170-194 (2012) · Zbl 1258.65045 · doi:10.1137/110835463
[29] Xue, J., Xu, S., Li, R.-C.: Accurate solutions of M-matrix algebraic Riccati equations. Numer. Math. 120, 671-700 (2012) · Zbl 1260.15025 · doi:10.1007/s00211-011-0421-0
[30] Xue, J., Ye, Q.: Entrywise relative perturbation bounds for exponentials of essentially non-negative matrices. Numer. Math. 110(3), 393-403 (2008) · Zbl 1163.65021 · doi:10.1007/s00211-008-0167-5
[31] Xue, J., Ye, Q.: Computing exponentials of essentially non-negative matrices entrywise to high relative accuracy. Math. Comput. 82(283), 1577-1596 (2013) · Zbl 1279.65051 · doi:10.1090/S0025-5718-2013-02677-4
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.