In: IEEE Transactions on Reliability, vol. 46, no. 3, pages 430-440. September 1997.
Abstract: Adaptive uniformization (AU) has recently been proposed as a method to compute transient measures in continuous-time Markov chains and has been shown to be especially attractive for solving large and stiff dependability models. The major advantage of AU is that it requires at most as many iterations as standard uniformization (SU), and often far fewer, thus resulting in substantial computational savings. However, this computational gain can be offset by the need to compute more complex "jump probabilities" in AU, whose computation is more expensive than computing Poisson probabilities in SU. In particular, it can be shown that AU is computationally superior to SU if and only if the considered time instant is less than some threshold time value. To overcome this drawback, we combine AU and SU such that AU is used over the start of the time interval of interest, while SU is applied to the rest of the time interval. We show that combined AU/SU can be implemented in ! such a way that the combination introduces only minor computational overhead, the number of iterations required is almost as low as AU, and the cost of computing the jump probabilities is as low as SU. Furthermore, combined AU/SU will be shown to yield a strict lower bound of the true result, within any desired pre-specified accuracy. The derived error bounds take into account the error introduced when the Fox/Glynn algorithm is used for computing Poisson probabilities, and we will enhance this algorithm to optimize its error bound characteristics. Implementations of SU and AU that are based on the Fox/Glynn method can benefit from these results, since more accurate error bounds can be determined. To demonstrate the benefits of combined AU/SU, we apply it to a machine-repairman model, using a version of combined AU/SU implemented in UltraSAN, a performance and dependability evaluation software package.
Keywords: Markov processes, Transient solution, Uniformization, Reliability evaluation, Dependability evaluation.