Componentwise accurate fluid queue computations using doubling algorithms
From MaRDI portal
Publication:2353379
Abstract: Markov-modulated fluid queues are popular stochastic processes frequently used for modelling real-life applications. An important performance measure to evaluate in these applications is their steady-state behaviour, which is determined by the stationary density. Computing it requires solving a (nonsymmetric) M-matrix algebraic Riccati equation, and indeed computing the stationary density is the most important application of this class of equations. Xue, Xu and Li [Numer. Math., 2012] provided a componentwise first-order perturbation analysis of this equation, proving that the solution can be computed to high relative accuracy even in the smallest entries, and suggested several algorithms for computing it. An important step in all proposed algorithms is using so-called triplet representations, which are special representations for M-matrices that allow for a high-accuracy variant of Gaussian elimination, the GTH-like algorithm. However, triplet representations for all the M-matrices needed in the algorithm were not found explicitly. This can lead to an accuracy loss that prevents the algorithms to converge in the componentwise sense. In this paper, we focus on the structured doubling algorithm, the most efficient among the proposed methods in Xue et al., and build upon their results, providing (i) explicit and cancellation-free expressions for the needed triplet representations, allowing the algorithm to be performed in a really cancellation-free fashion; (ii) an algorithm to evaluate the final part of the computation to obtain the stationary density; and (iii) a componentwise error analysis for the resulting algorithm, the first explicit one for this class of algorithms. We also present numerical results to illustrate the accuracy advantage of our method over standard (normwise-accurate) algorithms.
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 [\textit{X.-X. Guo} et al., Numer. Math. 103, No. 3, 393--412 (2006; Zbl 1097.65055)], and its variants, see [\textit{D. A. Bini} et al., Numer. Math. 116, No. 4, 553--578 (2010; Zbl 1202.15016)] or [\textit{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 [\textit{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.
Recommendations
- Fluid approximations for a processor-sharing queue
- Accuracy of fluid approximations for queueing systems with congestion-sensitive demand and implications for capacity sizing
- A FLUID FLOW APPROXIMATION ANALYSER FOR BUFFER TYPE QUEUEING SYSTEMS
- Queue-based random-access algorithms: fluid limits and stability issues
- Numerical methods for analysis of multiflow queuing systems with virtual partition of a common buffer
- Double-ended queues with non-Poisson inputs and their effective algorithms
- Exact solution to tandem fluid queues with controlled input
- Workload analysis of a two-queue fluid polling model
- Explicit and Iterative Numerical Approaches to Solving Queueing Models
Cites work
- A stochastic fluid model for an ad hoc mobile network
- A structure-preserving doubling algorithm for nonsymmetric algebraic Riccati equation
- Accuracy and Stability of Numerical Algorithms
- Accurate computation of the smallest eigenvalue of a diagonally dominant M-matrix
- Accurate solutions of \(M\)-matrix algebraic Riccati equations
- Aggressively truncated Taylor series method for accurate computation of exponentials of essentially nonnegative matrices
- Alternating-directional doubling algorithm for M-matrix algebraic Riccati equations
- An Identity for the Schur Complement of a Matrix
- Analysis of a Feedback Fluid Model for Heterogeneous TCP Sources
- Approximations of boundary crossing probabilities for a Brownian motion
- Computing exponentials of essentially non-negative matrices entrywise to high relative accuracy
- Entrywise relative perturbation bounds for exponentials of essentially non-negative matrices
- Experimental characterization and model identification of directional hardening effects in metals for complex strain path changes
- Fluid models in queueing theory and Wiener-Hopf factorization of Markov chains
- Functions of Matrices
- scientific article; zbMATH DE number 5872159 (Why is no real title available?)
- scientific article; zbMATH DE number 3760340 (Why is no real title available?)
- scientific article; zbMATH DE number 961607 (Why is no real title available?)
- Numerical Methods for Structured Markov Chains
- Numerical solution of algebraic Riccati equations.
- Simple models of network access, with applications to the design of joint rate and admission control.
- Solving quadratic matrix equations and factoring polynomials: new fixed point iterations based on Schur complements of Toeplitz matrices
- Stability for fluid queues: characteristic inequalities
- Stochastic Complementation, Uncoupling Markov Chains, and the Theory of Nearly Reducible Systems
- Stochastic theory of a fluid model of producers and consumers coupled by a buffer
- The Padé method for computing the matrix exponential
- The Scaling and Squaring Method for the Matrix Exponential Revisited
- Transforming algebraic Riccati equations into unilateral quadratic matrix equations
Cited in
(12)- Accurate numerical solution for structured \(M\)-matrix algebraic Riccati equations
- Palindromic linearization and numerical solution of nonsymmetric algebraic \(T\)-Riccati equations
- Highly accurate doubling algorithm for quadratic matrix equation from quasi-birth-and-death process
- Construction of algorithms for discrete-time quasi-birth-and-death processes through physical interpretation
- Matrix equations in Markov modulated Brownian motion: theoretical properties and numerical solution
- Slowing time: Markov-modulated Brownian motions with a sticky boundary
- Highly accurate doubling algorithms for \(M\)-matrix algebraic Riccati equations
- Highly accurate Latouche-Ramaswami logarithmic reduction algorithm for quasi-birth-and-death process
- Iterative and doubling algorithms for Riccati‐type matrix equations: A comparative introduction
- Numerical methods for QBD matrix equations
- Efficient computation of Wiener-Hopf factorization of Markov-modulated Brownian motion
- Accurate numerical solution for shifted M-matrix algebraic Riccati equations
This page was built for publication: Componentwise accurate fluid queue computations using doubling algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2353379)
