Back to Papers and Abstracts
Abstract: Many processes, particularly biological and chemical, are evanescent in nature, with eventual extinction certain. However, the time required for this to occur may be very long, and the process may appear stationary to observers. For example, an animal population may be subject to large scale mortality or emigration in response to various stimuli and, although stochastic models predict eventual extinction, it may survive for a long period until brought to a sudden end.
Such processes can be modelled by continuous-time Markov chains, characterised by the fact that they are absorbed, or "evanesce". In most practical applications the time to absorption is large, or at least large enough, and we are interested in the behaviour before evanescence. The equilibrium distribution is of no use, being concentrated on the absorbing state, so we use the quasi-stationary distribution (the long-term distribution, conditional on non-absorption).
Finding the quasi-stationary distribution is equivalent to finding the eigenvector of the smallest eigenvalue of the q-matrix of the Markov process restricted to the non-absorbing class. If the model is to be useful, this matrix is usually large, and even approximating by truncating the matrix leaves upwards of 10^8 elements in the matrix. Obviously, numerical methods, efficient ones, are required.
An aggregation/disaggregation method for determining the smallest eigenvalue and associated eigenvector has recently been developed and implemented in parallel on a 64 by 64 processor SIMD machine. The method outperforms standard methods such as inverse iteration using restriction operators which depend on the current `solution', and Jacobi iterations as smoothers. We will illustrate the method for epidemic, malaria and predator-prey models, and compare the performance with the serial implementation.
Acknowledgement: This worked was funded by the Australian Research Council.
The author:
Back to Papers and Abstracts
Last modified: 26th December 1995