** 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, , increases. For simplicity, assume
that the infinitesimal generator of the -th process is fixed while
the -th process is in levels for all (i.e.
), and that all the processes
have the same number of states, , in each level.

In DR, the order of the submatrices, , grows
double-exponentially with (i.e. ); specifically,
can be determined by the following recursive formula:
for and
, where is the number of phases used in a PH
distribution that approximates a (conditional) sojourn time in levels
(there are
types of sojourn times).
In DR-PI, the order of the submatrices, , grows
exponentially with :
. In DR-CI, the order of the submatrices, , grows
exponentially with (but slower than ) when :
, and it
grows linearly with when :
.

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