A symbolic multilevel method with sparse submatrix representation for memory-speed-tradeoff

Inhalt:
This paper is about the numerical analysis of Markov chains, employing a multilevel algorithm for computing the vector of steady-state probabilities. As a basic data structure, multi-terminal binary decision diagrams (MTBDD) are used, which are known to provide very space-efficient symbolic representations of the rate matrix, even for very large Markov chains. In the approach presented here, the original Markov chain and several aggregated chains (used during the multilevel cycles) are stored within a single MTBDD. It is also discussed how the problem of non-contiguous encodings of the reachable states (of both the original and the aggregated chains) is dealt with by the concept of multi-offset-labelling. Furthermore, as the major innovation of the paper, a modification of the symbolic data structure is presented, in which parts of the MTBDD are replaced by a new type of enhanced sparse-matrix format, thereby speeding up access to the matrix elements during iteration. This new memory layout, specially tailored for multilevel algorithms, follows the recursive block structuring which is characteristic for both the multilevel algorithm and theMTBDD-based representation. The proposed data structure and algorithm are evaluated on the basis of three benchmark models. The empirical results exhibit considerable improvements in speed at very low memory cost, when compared to other methods.