Transient solution of markov models by combining adaptive & standard uniformization

Summary & Conclusions -Adaptive uniformization (AU) has recently been proposed to compute transient measures in continuous-time Markov chains and is especially attractive for solving large & 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 computation savings. However, this computation 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, 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, AU & SU are combined (AU/SU) so that AU is used early in the time interval, and SU is used over the rest of the time interval. AU/SU can be implemented so that: 1) the combination introduces only minor computation overhead, 2) the number of iterations required is almost as low as for AU, and 3) the cost of computing the jump probabilities is about as low as for SU. AU/SU yields a strict lower bound of the true result, within any desired pre-specified accuracy. The error bounds include the error introduced when the Fox/Glynn algorithm is used for computing Poisson probabilities; this algorithm is enhanced to optimize its error-bound characteristics. Implementations of SU & AU that are based on the Fox/Glynn method can benefit from these results, since more-accurate errorbounds can be determined. To demonstrate the benefits of AU/SU, it is applied to a machine-repair model, using a version of combined AU/SU implemented in UltraSAN, a performance & dependability evaluation software package.