Computational Complexity Analysis of Determinant Decision Diagram
Computational Complexity Analysis of Determinant Decision Diagram
复制标题
DOI：
10.1109/tcsii.2010.2067791
复制
发表时间：
2010-10
期刊：
影响因子：
--
通讯作者：
G. Shi
中科院分区：
文献类型：
--
作者：
G. Shi
摘要-行列式判定图（DDD）使用二元判定图（BDD）符号化地计算行列式，然后将其应用于符号电路分析。这种技术的效率主要由符号排序方案确定。在BDD的实践中，寻找最佳符号顺序是一个非确定性的多项式时间难题。到目前为止，它是未知的最佳顺序是一般的稀疏矩阵。这篇简报表明，行（或列）顺序是全矩阵的最佳BDD顺序，因为所构造的DDD图具有最小数量的顶点（即，DDD大小）。证明了对于n × n全矩阵，最佳DDD长度为（n · 2n-1）.这个大小提供了一个DDD复杂性的措施，很少在文献中进行了调查。
Abstract-A determinant decision diagram (DDD) uses a binary decision diagram (BDD) to calculate a determinant symbolically, which is then applied for symbolic circuit analysis. The efficiency of such a technique is determined mainly by a symbol ordering scheme. Finding an optimal symbol order is an non-deterministic polynomial-time hard problem in the practice of BDD. So far, it is unknown what an optimal order is for a general sparse matrix. This brief shows that a row-wise (or column-wise) order is an optimal BDD order for full matrices in the sense that the DDD graph constructed has the minimum number of vertices (i.e., the DDD size). The optimal DDD size is proven to be (n · 2n-1) for an n × n full matrix. This size provides a DDD complexity measure that has rarely been investigated in the literature.