Matrix analytic method

B_0 & B_1 & B_2 & B_3 & \cdots \\ A_0 & A_1 & A_2 & A_3 & \cdots \\ & A_0 & A_1 & A_2 & \cdots \\ & & A_0 & A_1 & \cdots \\ \vdots & \vdots & \vdots & \vdots & \ddots \end{pmatrix} where *B**i* and *A**i* are *k* × *k* matrices. (Note that unmarked matrix entries represent zeroes.) Such a matrix describes the embedded Markov chain in an M/G/1 queue. If *P* is irreducible and positive recurrent then the stationary distribution is given by the solution to the equations ::P \pi = \pi \quad \text{ and } \quad \mathbf e^\text{T}\pi = 1 where **e** represents a vector of suitable dimension with all values equal to 1. Matching the structure of *P*, *π* is partitioned to *π*1, *π*2, *π*3, …. To compute these probabilities the column stochastic matrix *G* is computed such that :: G = \sum_{i=0}^\infty G^i A_i. *G* is called the auxiliary matrix. Matrices are defined ::\begin{align} \overline{A}_{i+1} &= \sum_{j=i+1}^\infty G^{j-i-1}A_j \\ \overline{B}_i &= \sum_{j=i}^\infty G^{j-i}B_j \end{align} then *π*0 is found by solving ::\begin{align} \overline{B}_0 \pi_0 &= \pi_0\\ \quad \left(\mathbf e^{\text{T}} + \mathbf e^{\text{T}}\left(I - \sum_{i=1}^\infty \overline{A}_i\right)^{-1}\sum_{i=1}^\infty \overline{B}_i\right) \pi_0 &= 1 \end{align} and the *π**i* are given by **Ramaswami's formula**, a numerically stable relationship first published by Vaidyanathan Ramaswami in 1988. ::\pi_i = (I-\overline{A}_1)^{-1} \left[ \overline{B}_{i+1} \pi_0 + \sum_{j=1}^{i-1} \overline{A}_{i+1-j}\pi_j \right], i \geq 1. ## Computation of ''G'' There are two popular iterative methods for computing *G*, - functional iterations - cyclic reduction. ## Tools - [MAMSolver](http://www.cs.wm.edu/MAMSolver/) ## References ## References 1. (2012). "Performance Modeling and Design of Computer Systems". 2. (1984). "Matrix-analytic methods in queuing theory". *European Journal of Operational Research*. 3. (1997). "An improved FFT-based version of Ramaswami's formula". *Communications in Statistics. Stochastic Models*. 4. (2005). "Bridging ETAQA and Ramaswami's formula for the solution of M/G/1-type processes". *Performance Evaluation*. 5. (2002). ["Performance Evaluation of Complex Systems: Techniques and Tools"](https://archive.org/details/performanceevalu0000unse/page/36). 6. (2006). "Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications". *John Wiley & Sons, Inc*. 7. (2008). "Retrial Queueing Systems". 8. (2002). "Exact aggregate solutions for M/G/1-type Markov processes". *ACM SIGMETRICS Performance Evaluation Review*. 9. (1988). "A stable recursion for the steady state vector in markov chains of m/g/1 type". *Communications in Statistics. Stochastic Models*. 10. (2005). "Numerical Methods for Structured Markov Chains". 11. (1998). "Solving m/g/l type markov chains: Recent advances and applications". *Communications in Statistics. Stochastic Models*. 12. (2002). "Computer Performance Evaluation: Modelling Techniques and Tools". ::callout[type=info title="Wikipedia Source"] This article was imported from [Wikipedia](https://en.wikipedia.org/wiki/Matrix_analytic_method) and is available under the [Creative Commons Attribution-ShareAlike 4.0 License](https://creativecommons.org/licenses/by-sa/4.0/). Content has been adapted to SurfDoc format. Original contributors can be found on the [article history page](https://en.wikipedia.org/wiki/Matrix_analytic_method?action=history). ::