next up previous contents
Next: Moments of inter-level passage Up: Approximations of dimensionality reduction Previous: Dimensionality reduction with complete   Contents


Computational complexity of DR, DR-PI, and DR-CI

When DR, DR-PI, and DR-CI are applied to an RFB process, their running times differ primarily due to the differences in the orders of the submatrices of the generator matrix (the number of states in each level) of the 1D Markov chain reduced from the RFB process. Below, we compare how the orders of the submatrices of DR, DR-PI, and DR-CI grow as the number of processes, $m$, increases. For simplicity, assume that the infinitesimal generator of the $i$-th process is fixed while the $(i-1)$-th process is in levels $\geq\kappa$ for all $i$ (i.e. $\kappa=\kappa_1=\cdots=\kappa_{m-1}$), and that all the processes have the same number of states, $\xi$, in each level.

In DR, the order of the submatrices, $S_{DR(m)}$, grows double-exponentially with $m$ (i.e. $O(2^{2^m})$); specifically, $S_{DR(m)}$ can be determined by the following recursive formula: $S_{DR(m)} = \kappa S_{DR(m-1)} + (S_{DR(m-1)})^2N_{PH}$ for $m>1$ and $S_{DR(1)}=\xi$, where $N_{PH}$ is the number of phases used in a PH distribution that approximates a (conditional) sojourn time in levels $\geq\kappa$ (there are $(S_{DR(m-1)})^2$ types of sojourn times). In DR-PI, the order of the submatrices, $S_{PI(m)}$, grows exponentially with $m$: $S_{PI(m)} = (\kappa+N_{PH})^{m-1} \xi$. In DR-CI, the order of the submatrices, $S_{CI(m)}$, grows exponentially with $m$ (but slower than $S_{PI(m)}$) when $\kappa>1$: $S_{CI(m)} = \kappa^{m-1}\left(\xi+N_{PH}/(\kappa-1)\right)-N_{PH}/(\kappa-1)$, and it grows linearly with $m$ when $\kappa=1$: $S_{CI(m)} = (m-1) N_{PH} + \xi$.

next up previous contents
Next: Moments of inter-level passage Up: Approximations of dimensionality reduction Previous: Dimensionality reduction with complete   Contents
Takayuki Osogami 2005-07-19