A Symbolic Multilevel Method with Sparse Submatrix Representation for Memory-Speed-Tradeoff
A Symbolic Multilevel Method with Sparse Submatrix Representation for Memory-Speed-Tradeoff
复制标题
一种用于内存速度权衡的稀疏子矩阵表示的符号多级方法
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Markus Siegle
中科院分区：
文献类型：
--
作者：
Johann Schuster;Markus Siegle
本文是关于马尔可夫链的数值分析，采用多级算法计算稳态概率向量。作为一个基本的数据结构，使用多终端二进制决策图（MTBDD），这是已知的，提供非常节省空间的符号表示的速率矩阵，即使是非常大的马尔可夫链。在这里提出的方法中，原始马尔可夫链和几个聚合链（在多级循环中使用）存储在一个MTBDD中。还讨论了如何通过多偏移标记的概念来处理可达状态（原始链和聚合链）的非连续编码问题。此外，作为本文的主要创新，提出了一种修改的符号数据结构，其中部分MTBDD被替换为一种新型的增强稀疏矩阵格式，从而加快了在迭代过程中访问矩阵元素。这种新的内存布局，专门为多级算法定制，遵循递归块结构，这是多级算法和基于MTBDD的表示的特点。所提出的数据结构和算法的基础上，三个基准模型进行评估。实证结果显示，在非常低的内存成本的速度相当大的改善，与其他方法相比。
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 the MTBDD-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.