Inexact Uniformization Method for Computing Transient Distributions of Markov Chains

The uniformization method (also known as randomization) is a numerically stable algorithm for computing transient distributions of a continuous time Markov chain. When the solution is needed after a long run or when the convergence is slow, the uniformization method involves a large number of matrix...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on scientific computing 2007-01, Vol.29 (6), p.2562-2580
Main Authors: Sidje, Roger B., Burrage, Kevin, MacNamara, Shev
Format: Article
Language:English
Subjects:
Accuracy
Algorithms
Approximation
Cost control
Markov analysis
Methods
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The uniformization method (also known as randomization) is a numerically stable algorithm for computing transient distributions of a continuous time Markov chain. When the solution is needed after a long run or when the convergence is slow, the uniformization method involves a large number of matrix-vector products. Despite this, the method remains very popular due to its ease of implementation and its reliability in many practical circumstances. Because calculating the matrix-vector product is the most time-consuming part of the method, overall efficiency in solving large-scale problems can be significantly enhanced if the matrix-vector product is made more economical. In this paper, we incorporate a new relaxation strategy into the uniformization method to compute the matrix-vector products only approximately. We analyze the error introduced by these inexact matrix-vector products and discuss strategies for refining the accuracy of the relaxation while reducing the execution cost. Numerical experiments drawn from computer systems and biological systems are given to show that significant computational savings are achieved in practical applications.
ISSN:1064-8275
1095-7197
DOI:10.1137/060662629