“Matrix geometric method”的意思、由来-开放百科全书

In probability theory, the matrix geometric method is a method for the analysis of quasi-birth–death processes, continuous-time Markov chain whose transition rate matrices with a repetitive block structure.^[1] The method was developed "largely by Marcel F. Neuts and his students starting around 1975."^[2]

Method description

The method requires a transition rate matrix with tridiagonal block structure as follows

where each of B₀₀, B₀₁, B₁₀, A₀, A₁ and A₂ are matrices. To compute the stationary distribution π writing π Q = 0 the balance equations are considered for sub-vectors π_i

holds where R is the Neut's rate matrix,^[3] which can be computed numerically. Using this we write

which can be solve to find π₀ and π₁ and therefore iteratively all the π_i.

Computation of R

The matrix R can be computed using cyclic reduction^[4] or logarithmic reduction.^[5]^[6]

Matrix analytic method

The matrix analytic method is a more complicated version of the matrix geometric solution method used to analyse models with block M/G/1 matrices.^[7] Such models are harder because no relationship like π_i = π₁ R^i – 1 used above holds.^[8]

External links

References

1. ^{{cite book|first=Peter G.|last=Harrison|authorlink=Peter G. Harrison|first2=Naresh M.|last2=Patel|title=Performance Modelling of Communication Networks and Computer Architectures|publisher=Addison-Wesley|year=1992|pages=317–322|isbn=0-201-54419-9}}
2. ^{{Cite book | first1 = S. R. | last1 = Asmussen| doi = 10.1007/0-387-21525-5_8 | chapter = Random Walks | title = Applied Probability and Queues | series = Stochastic Modelling and Applied Probability | volume = 51 | pages = 220–243 | year = 2003 | isbn = 978-0-387-00211-8 | pmid = | pmc = }}
3. ^{{Cite journal | last1 = Ramaswami | first1 = V. | doi = 10.1080/15326349908807141 | title = A duality theorem for the matrix paradigms in queueing theory | journal = Communications in Statistics. Stochastic Models | volume = 6 | pages = 151–161 | year = 1990 | pmid = | pmc = }}
4. ^{{Cite journal | last1 = Bini | first1 = D. | last2 = Meini | first2 = B. | doi = 10.1137/S0895479895284804 | title = On the Solution of a Nonlinear Matrix Equation Arising in Queueing Problems | journal = SIAM Journal on Matrix Analysis and Applications | volume = 17 | issue = 4 | pages = 906 | year = 1996 | pmid = | pmc = }}
5. ^{{cite journal | year = 1993 | title = A Logarithmic Reduction Algorithm for Quasi-Birth-Death Processes | journal = Journal of Applied Probability | volume = 30 | issue = 3 | pages = 650–674 | publisher = Applied Probability Trust | jstor = 3214773 | url = | format = | accessdate = | first1 = Guy | last1 = Latouche | first2 = V. | last2 = Ramaswami}}
6. ^{{Cite journal | last1 = Pérez | first1 = J. F. | last2 = Van Houdt | first2 = B. | doi = 10.1016/j.peva.2010.04.003 | title = Quasi-birth-and-death processes with restricted transitions and its applications | journal = Performance Evaluation| volume = 68 | issue = 2 | pages = 126 | year = 2011 | url = http://www.doc.ic.ac.uk/~jperezbe/data/PerezVanHoudt_PEVA_2011.pdf| pmid = | pmc = }}
7. ^{{Cite book | last1 = Alfa | first1 = A. S. | last2 = Ramaswami | first2 = V. | doi = 10.1002/9780470400531.eorms0631 | chapter = Matrix Analytic Method: Overview and History | title = Wiley Encyclopedia of Operations Research and Management Science | year = 2011 | isbn = 9780470400531 | pmid = | pmc = }}
8. ^{{cite book|first1=Gunter|last1= Bolch|first2=Stefan |last2= Greiner |first3=Hermann |last3=de Meer |first4= Kishor |last4= Shridharbhai Trivedi | year=2006| edition=2 | page=259| title=Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications |publisher= John Wiley & Sons, Inc|isbn=0471565253}}