139×网址：http://www.elsevier.nl/locate/entcs/volume66.html15页实数和BDD也不知道。Müller1AbteilungInformatikUniversitüatTrierD-54286 Trier，Germany摘要我们提出了一个建议，表示大向量的实数使用二元决策图（BDDs）。如果向量包含结构化数据，则与数字的显式表示相比，所需的大小可以显著减少我们能够证明一个非平凡的上限为这个大小的一个理论上的例子：表近似线性函数。1介绍在实际计算中使用实数通常需要大量的数据。典型的例子是应用程序从嵌入理论或从随机Petri网，涉及的线性方程的解决方案n n-矩阵，其中对于目前的技术n可以选择的顺序在约10 -8。以常规方式存储相应的矩阵将需要大约1016个条目，这将需要使用8字节IEEE双格式的大约1亿GB的存储器。即使只是存储一个大小为n的解向量，也需要将近1 GB的内存。通常，使用的矩阵不是通常意义上的稀疏矩阵，甚至可能几乎所有的元素都是非零的。相反，它们通常具有内部结构，可以使用决策图或基于Kronecker的方法[3]等技术来利用，从而减少存储矩阵所需的内存这里，矩阵中的不同值的数量仍然很小，并且这些值被显式存储。然而，通常解向量的所有分量都是不同的，因此在这里，值的显式存储为易处理的问题大小构建了一个自然的界限但是，我们经常在解向量中有一些内部结构，尽管几乎所有的值都是不同的：1电子邮件：mueller@uni-trier.de，网址：http：//www.informatik.uni-trier.de/2002年由ElsevierScienceB出版。 诉 操作访问根据C CB Y-NC-N D许可证进行。140→|−|≤∈≤从量子理论中得出的结果要么具有所谓的乘积形式，要么表现出几乎几何衰减的行为。另一个问题是结果的可靠性，其中可能需要提高精度甚至精确的算术那么每个单个值显然需要远远超过IEEE双格式的通常8字节。以合理的精度获得结果所需的内存甚至可能取决于底层矩阵。使用高斯消去法的精确算术包[7]的实验表明，例如，对于希尔伯特矩阵，大小n=250已经可以在中间结果中导致每个数字大约1KB（已经导致每个这种大小的矩阵大约60MB），以获得8字节的最终结果。克服这些内存限制的一种可能性可能在于通过二进制决策图（BDD）对实数的隐式表示我们将把这些与有符号数字的概念结合起来，以减少压缩存储格式带来的复杂性增加目前，我们正在评估一个原型实现。由于这个原型还不够复杂，无法在现实世界的问题上进行测试，我们将使用一个相当理论化的问题来确定可能的增益：在Type-2-Theory of E-ectivity（TTE，参见例如[11]）中，通常使用显式方法来表示数字。 当考虑（空间或时间）复杂度时，这仅仅因为表示而导致时间复杂度的下限。 例如，要表示函数f：[0， 1] R在TTE中，可以使用等距坐标处的值表使用线性插值该表定义了对f的逐步线性函数近似：f是一个1M2M3M4M...m−1MMMf（1）f（2）f（3）f（4）嗯嗯嗯...f（m−1）f（m）MM带误差逼近可导函数f2-n，我们需要（2）n = O（2）n = O（1）n= O（2）n[0， 1]。 所以这是一个 一个简单的，虽然是理论上的例子，使用了具有明显结构的值作为如何使用决策图来存储此类数据的示例，考虑长度为16的向量（0， 1， 2， 3， 0， 0， 0，0， 0， 0，0，0，0， 0， 0，0， 0）这里我们需要4位来表示所有可能的索引，其中条目#2将由值为2的位0010假设我们要使用24位（= 8个八位字节），每个值的（绝对）精度为2−12。然后，我们将使用3位来寻址这8个八位字节。这意味着决定图1中的矢量的示意图，其中细节将在下一部分中解释。该图遵循例如[1，9]中的绘图约定：一边绘制为实心，零边绘制为虚线。141具有值2的条目#2即索引位0010：p2 p1均p0重量值0008−400018−300108−200118−10100802101810110820111830图1.一、8-sdBDD示例2使用BDD为了用普通的显式方法表示对单个数的逼近，通常使用由一个整数和一个双向量组成的t_up_e（l，B）B=. b2b1b0，表示dyadicnumber2l·bj2j。这对应于二进数的通常半对数表示，例如，在IEEE标准的标准。我们在这里不考虑符号位，因为稍后使用有符号数字时它们将被淘汰。使用这样的半对数表示和BDD，我们可以在两个方向上进行：(i) 将精确近似值存储到单个数字（即非常长的位向量）。(ii) 在一个BDD中存储大量不同的中等精度的数字如果我们必须以一定的规律存储大量数据，第一种方法可能是有希望的算术运算可能变得非常快，例如，两个数的和可以在向量长度为对数的多个BDD运算中计算（如果使用有符号数字，则不需要进位，参见下一节）由于BDD允许相当简单地访问某些子结构，因此像Karatsuba算法这样的递归乘法方案应该很容易实现。第二种方法的目的是在非常大的线性系统的解决方案中提到的介绍。在下文中，我们将尝试同时遵循两个方向：当从索引集I一次性近似i的几个数字x i时，我们不使用这些双向量的several. b2，ib1，ib0，iasin根精确位0p_0精确位1p_1精确位2p_2索引位3i_3索引位2i_2索引位1i_1索引位0i_0 i_03 102142{−}联系我们一个传统的表示，而是用一个函数F（p，i）：P×I→D代替所有的位向量，这样每个xi可以从位置集合P的位置p处的数字dp，i：=F（p，i）重构。的优点这种方法的一个优点是，如果一组数xi包含足够的规律性，那么通过决策图表示函数F可能会导致非常短的表示。从这些决策图的许多不同版本中，我们将使用简化有序二元决策图（ROBDD）。对于这种数据结构的介绍，参见例如[1，10]。这种类型的图的优点是ROBDD是函数的规范表示，其中图中的所有超连续节点都已被删除。如果D有两个以上的元素，那么这种类型的BDD的一般命名是多端BDD（MTBDD）。我们使用一种特殊类型的有符号数字表示来代替简单的二进制表示，即我们使用BDD来存储函数F：P×I→Dr，将Dr中的数字分配给P中的位置，并将索引分配给I. BDD的终端节点现在携带来自有限数位集r+1（一）D r：={n∈ Z，|n| ≤[ 2|}对于任意自然基数r>4。例子是D5={− 3，...，3}，或D8= 5，...，五、具有来自Dr的终端节点的MTBDD将被称为r-sdBDD（带符号的数字BDD）。这种选择的Dr的动机将在下一节给出的一般考虑有符号的数字算术。为了简单起见，我们将使用以下索引集I k，并将单个索引i ∈ I k的相关二进制表示法作为二进制向量（i k−1i k−2. i0）：克-1（二）I k：={0，.，2 k−1}，编码i =v=0第一卷第二卷对于个位数的位置，我们使用以下集合P n，同样使用二进制记法（p n−1p n−2..p0）的单个位置p∈ Pn：（三）P n：={− 2 n−1，.，2n−1−1}，编码p=乌斯季-1v=0pν2ν−2n−1这里使用了类似于IEEE浮点数中的指数格式的有偏二进制表示法因此，r-sdBDD将使用n+k个二进制变量，这些变量的顺序如下（稍后将解释）：(4)（p0，p1，.，p n−1，i k−1，i k−2，.i0）Anysuc hr-sdBDDA定义一个函数fA：0，1n+kDr. 这个函数的值被定义为通过A的路径上的叶子上的数字，对应于n+k个变量的给定值。使用给定143因此，二进制变量上的这个函数f A现在可以被解释为f。函数FA：Pn×Ik→Dr，利用这个函数FA，我们定义了向量x A（0），.， x A（2 k−1）存储在A中的数值，Σ（五）xA（i）：=p∈PnFA（p，i）·rp选择n = 3，k = 4，向量（0，1，2，3，0. 0）的长度为2k = 16，由引言中给出的图表示，当解释为8-sdBDD时。显然，在使用一组位向量的普通显式表示和使用单个二元决策图的隐式表示之间存在可计算的转换当然，这种转换需要建筑物的响应。遍历许多图，因此可能具有高计算复杂度。即使所有的xA（i）都是不同的，仍然有可能的是，转换到隐式表示可以几何地减少存储器的量，而从r-sdBDD到显式形式的逆变换可以指数地增加它。基数r的大小的作用有点违反直觉：一方面，使用较大的r值具有直接的优势，即减少了数字位置所需的变量数量n。另一方面，更大的可能终端节点集可能会减少数据中的结构，从而导致BDD内部的更多内部节点 在[10]中，不鼓励使用2个以上的终端节点，因为较大的数字总是可以用小的终端决策图（具有二进制终端节点）代替。然而，我们将在下文中使用r >4，因为它允许更简单的算法公式化。普通的64位IEEE浮点标准（“double”）和上面定义的BDD格式之间的一个重要区别在BDD中，通过定义Pn，基本上共享指数l：=−2n−1，xA（i）在（3）和（5）中。为了覆盖甚至扩展双精度格式，n和r必须足够大：由于双指数的长度固定为11位，因此r和n必须选择为r2n>2211，即n+ log2 log2r > 11。使用r= 16，已经有n= 9个位置变量;n= 10，最小值r= 5将足以覆盖大约2300位的范围，已经明显大于双精度数的范围。ROBDD的一个重要问题是变量的排序，在决策图中的每条路径上必须相同这种排序可能会戏剧性地增加BDD的大小，并因此增加计算复杂度。因此，一个主要的问题是，是否将编码数字位置p的变量放在编码数字xA（i）的索引i首先放置位置变量简化了算术运算，因为r-sdBDD已经包含了相同位置的数字但是在这种情况下，对单个值xA（i）的所有数字的访问意味着针对每个144|| ≤−#Pn= 2n个位置。我们认为，对于所考虑的应用，算法操作比单个变量的提取更重要，因此位置在索引应该是更好的顺序。另外，考虑到所有xA（i）都不同的情况，位置之前的排序索引将意味着BDD需要宽度#Ik= 2k来存储2k个值，因此在这种情况下根本不会减少内存稍后将讨论（4）中的变量的排序的进一步细节。3带符号数位算术考虑到我们想要使用相当大的数字向量来表示数字的目的，即使是像简单的全加器这样的自然算法来添加关于进位的两个数字也变得有问题：当应用于我们的BDD方法时，进位传播将导致加法的序列化，这将需要太多的时间。即使是通常的算法来加速进位传播也没有很大的帮助。因此，在我们的情况下，应该使用有符号数字算术，其中Avizienis的原始论文[2]已经考虑了算术运算的并行执行在本文的上下文中，并行化的可能性导致算法，非常适合BDD。有符号数字的优点是可以实现无进位加法（和减法），这在这里是最重要的有几种实现这种免携带添加的在[2]中已经可以找到以下内容，但我们以更适合我们的目的的方式来表达它。pose：对于由数字序列（... x j x j−1.. . ）和（. y j y j−1.. . 在基数为r的有符号数字系统中，首先给出了两个新的传送数字序列（... t j t j−1.. . ）和中间总和（. w j w j−1.. . ）以下面定义的方式计算，然后应用移位运算uj：= t j−1，最终中间体wj和移位的uj的和s j：= w j+ u j给出结果（. s j sj−1.. . ），其值为x+y。具体地，我们令r·tj+wj：=xj+yj。这并没有明确定义tj，wj，所以我们可以例如使用以下设置xj+yj≥r/ 2<$tj：= 1，wj：=xj+yj−r|r/ 2 t j：= 0，w j：= x j + yj|2. 当然，也有免携带附加145−- −−{−}-−2r+1x·jm−1r>rj{− −}−Σ(or而是有限进位），即使对于基数R= 2，但是它们使用附加的移位操作。我们在此不再赘述 例子可以在[8]中找到。基数r = 2的有符号数字已经在TTE中使用，以便获得允许定义计算复杂性的实数的简单表示，参见例如[5，6]。这里有一个规范化约束是必要的：为了得到一个数字的拓扑紧凑名称集，从1， 0， 1开始的两个非零数字必须不是“1 1”或“1 1”的形式 1'. 的 如果使用基数r大于2的有符号数字，则同样的想法也适用：这里，归一化约束将是前两位数字可以既不是不幸的是，无进位加法可能会产生禁止的形式 一个简单的例子（对任何r> 3都有效）是序列（. 0 3 1r 1r... . ）和（. 0 1 1 R1 R. . . ）导致总和 形式（…011 r.. . ）.在使用BDD的实现中，这将导致数字内的结构的不必要的减少，从而导致不必要的更大的图。此外，很难计算数字大小的界限，这会减慢乘法算法。这个规范化问题的一个可能的解决方案是禁止数字r-1和1-r完全相同。为了提高后一种BDD算法的速度公式，我们甚至进一步将数字集限制为D r：={-[r+1|、...、0，...，[r+1|}2 2其中[r+1|<当r> 4时，r-1成立。请注意，这组数字非常大，因为我们仍然可以将任何i∈Z写成i=rq+p的形式，其中q∈Z且p∈Dr。此外，还可以进行免携带添加：|x i + y i| ≤ r +2意味着|w i| ≤[二|-1且s j∈ D r。有符号数字表示的三个重要属性应该是：这里提到(i) 虽然我们有一个冗余表示，但只有一种可能性可以用有限个数字来表示零：所有数字本身都必须是(ii) 数字的符号就是第一个非零数字的符号(iii) 如果我们有r >4和上面的数字集Dr，那么另外.......j∈Z对于任何序列（. x j x j−1.. . ），如果m是最重要的非零数字的位置。与具有终端节点0的BDD相比，... r1，数字为1r，...，r 1几乎使终端节点的数量加倍。BDD软件包中的缓存策略将rm+1...146R◦·P虽然冗余度高可以弥补这一点，但冗余度高将导致数据中的结构较少使用Dr，我们最多有r+3个终端节点，这与关于算术的优点相比是微不足道的增加，这将在下面的部分中讨论4r-sdBDD上的基本操作在下文中，我们将定义r-sdBDD上的一些运算，稍后将用于定义基本算术。 为了简单起见，我们将用它们唯一对应的位向量来标识i ∈ I k或p ∈Pn，如（2）和（3）中所示。• 对r-sdBDD的操作可以基于BDD的通用算法，请参见例如[1]：如果n：B2→B或n：D2→Dr是对的基本结构的位B或有符号的数字Dr，那么我们可以将其扩展到BDD以下著名的香农扩展：n（0，x1，. . ），如果x0= 0f（x0，x1，.. . ）=的1，x1，. . ），如果x0= 1我们可以假设，对于这些基本运算的任何一个，它们都是关于BDDs A，B的一个广义运算，使得A∈B是一个请注意，BDD级别本质上是对单个值的操作的并行执行我们将把这个规范扩展用于普通的算术和逻辑符号，如'+'，'0'，'statist'，'0'，...。 以及布尔值到有符号数字0和1的隐式转换。 当然，在Dr的情况下，算术运算仅限于Dr，通常取模w.r.t. R.• BDD上的另一个基本操作是将布尔变量固定为特定值。 我们用A来表示|v：=bforavariablee vandabololeanvalueb. 函数FA（·）的结果是，ν=<$b将被相应参数上的数字所取代，但其中ν=b。 例如，向量x B对于B：= A|i0：= 0包含值xB（2i）=xB（2i +1）：=xA（2i），即这里所有值xA（）将被复制到不均匀的位置。当然，我们有几个固定的 值 ， 如 果 j∈Ik ，B=A|i ： =j是常数向量的BDD，其中x B（i）= x A（j），对于所有i∈I n。同样，B=A|p：=q是与位置q∈Pn对应的所有数字的BDD。• 对于给定的数z，n（z）表示具有z作为值的BDD，与索引i无关：xPn（z）（i）=z1472PP|P这里，z必须用一个带有位置P n的r-sdBDD表示表，即。we必须有z = z·r−2n−1 对于z∈Z，|z| ≤注意，Pp∈Pn[r+1|·r p。请n（z）不是唯一的，因为有符号数位中存在冗余陈述！• 给定一个指数j∈Ik，j的指示符将是r-sdBDDIk（j）such的FIk（j）（p，i）=1，i=j0，否则该指标Ik（j）的数值并不重要，但可用于选择数值。例如，B：=Pn（z）·Ik（j）表示向量xB，xB（i）=z，i=j0，否则显然，r-sdBDD的基本算术算法可以从两个操作中构建：（a）从r-sdBDDA中提取值xA（j）或（b）将r-sdBDD中的单个xA（j）更新为新值。这两个操作都可以分两步执行：一边是数字z和它的BDDn（z）之间的转换，另一边是对BDD的操作从z到n（z）可以使用普通（但进化）的算法用于构建BDD。从Pn（z）到z的逆转换简单地是（5）的求值。在下文中，我们将假设数值z已经作为BDD Pn（z）给出。因此，提取问题的解决方案简单地是限制Ai：=j一个BDDA到一个索引j。更新过程通常将改变r-sdBDD的结构，并且可以定义为B：=A·<$Ik（j） +Pn（z）·Ik（j），导致xB（i）=z，i=jxA（i），否则请注意，定义B的表达式中的所有运算符都是规范的BDD-初等算子在B或有符号数Dr上的推广！原则上，所有必要的算术运算都可以简化为这两个基本过程，再加上n（z）的计算或构造，以及显式数的普通算术。当然，我们的主要兴趣在于这些转换在空间或时间上过于消耗的情况。5r-sdBDDs上的算法虽然基于上面的提取和更新算法的算术比使用显式表示的算术慢得多，但算术148|||||当同时应用于r-sdBDD中的所有数字时，运算可能会更快：例如，符号的反转甚至可以通过简单地反转少数终端节点的值来在恒定时间内完成;下面将考虑两个r-sdBDD的值的分量加法和减法BDD对矩阵运算的适用性在很久以前就已经讨论过了，参见例如。[4]，结果总体上是积极在本文中，我们将把自己限制在初等算术。前面已经解释了使用有符号数字的无进位加法的算法其几乎所有组件都可以立即转移到BDD操作。唯一重要的部分是必要的数字移位移位对于乘法也非常重要，即使是像Karatsubas方法这样的高级算法，使用数字分解成结构良好的部分，也非常适合BDD。给定一个r-sdBDDA，下面的表达式定义了一个BDDB，其中所有值的所有数字都移动了一个位置。B：=A|p0：=0·p0+ 一|p0：=1，p1：=0·（p0= 0 <$p1= 1）+A|p0：=p1：=1，p2：=0·（p0=p1=0<$p2=1）+A|p0：=p1：=p2：=1，p3：=0·（p0=p1=p2=0<$p3=1）加...+A|p0：=.. . ：=pn−2：=1，pn−1：=0·（p0=. . . =pn−2=0<$pn−1=1）这里加法和乘法运算符再次表示典型的BDD-扩张。乘法运算符右边的布尔表达式表示相应布尔函数的BDD。把A分解成A|p0：=0，A|p0：=1，p1：=0等，在乘法运算器的左边，可以通过“分裂”A来计算迭代。|... ：=pj−1：= 1intoA. ：=pj−1：=1，pj：=0和A. ：=pj−1：=pj：= 1。如果BDD中的变量排序是如在（4）中（即，低位在高位之前在索引之前），则至少该分解几乎是免费的，因为它简单地包括返回1，1，1，.. . - BDD的分支。这里唯一没有移位的数字是在特殊位置p0=. =pn−1= 1，即在p= 2n−1−1 =max（Pn）。由于使用Dr的隐式归一化，如果这些位置上的数字之一不为零。过流条件可以很容易地检验，如图A p0：=...... ：=pn−1：=1当且仅当所有这些数字都为零时，它将与终端节点0相同。同样，我们能够实现多个位置的移位在下文中，我们将使用运算符B：=shift（A，m）（对于r-sdBDDA和整数m）来表示A中的数字已经移位了m个位置（在m>0的情况下向左移位，在m0的情况下向右移位）。除非有上半行或下半行，否则这种移位对应于所有值，即xB（i）=xA（i）·rm。149·|···◦◦||≤||||j=0◦≤||||◦ν−1为了实现两个r-sdBDD的加法，我们可以将传输数字t（x，y）、中间和w（x，y）以及普通和x+y（模r）的计算作为对Dr的初等运算。则所有值的加法ad d（A，B）都是-sdBDDsA，B（即. xadd（A，B）（i）=xA（i）+xB（i））简单地是add（A，B）：=w（A，B）+shift（t（A，B），1）这个加法的复杂度是O（n）BDD-操作。以类似的方式，我们能够实现学校男生乘法实现mult（A，B）的算法，其中xmult（A，B）（i）=xA（i）xB（i）。因此，这可以被实现为使用限制Ap：=q到单个位置、移位和加法的BDD算法，如果我们还使用初等算术函数prod和carry的规范BDD扩展，则在Dr上填充prod（x，y）+carry（x，y）r=xy。 我们在这里不会详细讨论，而只是说明使用这个简单乘法方案的mult（A，B）的复杂度是O（n2n）BDD操作。这个界限基本上来自一个因子中的2n个可能的位置，每个位置都导致n中的线性移位和加法。6空间上界我们已经提到，对于终端节点上的任何操作，有标准的方法在BDDX和Y上执行Z=X Y。使用单位成本度量并且在散列可以在O（1）中完成的假设下，这些操作的复杂度c（，X，Y）由X和Y的大小（即BDD中的节点数）确定：以及ZXY.这仍然意味着BDD在几个操作中的巨大增长，类似于有理算术中数字大小的爆炸因此，检查所考虑的BDD的空间复杂度非常重要，因为它也是时间复杂度的基本组成部分。在下面，我们首先给出一个关于任意ROBDD的大小的著名结果的证明，这将引导我们在以后的特殊情况下得到一个上界。引理6.1（例如[10]）考虑不超过ν个变量且至多两个不同终端节点的ROBDD。(a) 这些ROBDD的数目N（ν）以22ν+1为界。Σ(b) 这些ROBDD的大小S（ν）由min{2j，N（ν−j）}限定。因此，我们有S（v）= O（2 v/v）。证据（a）对于v= 0，正好有2个ROBDD，即终端节点0或1。如果v= 1，则只有两个另外的可能的ROBDD具有不同的终端节点，因此N（1）= 4。对于一个至多ν>1个变量的非平凡ROBDD，根必须有两个不同的分支，两个分支都至多有ν−1个变量。因此，N（v）≤150−··−2··≈→2›→2N（ν−1）·（N（ν−1）−1）+2≤N（ν−1）2。一个简单的归纳论证表明N（ν）≤ 22ν+1。(b) 假设v0，… v v−1是v变量在罗伯特·A.所以用变量vj标记的节点数是微不足道的以2j为界，因为到这样的节点的每条路径具有至多j的长度，并且因为节点可以具有至多两个后继节点。 另一方面，这些节点中的每一个都是ROBDD的根，其中最多νj变量，所有必须是不同的，因为ROBDD通过定义而减少。这意味着第二界N（ν−j）在最小值。计算上述公式中的最小值会导致阶的界2ν/ν对于具有ν个变量的ROBDD。我们甚至可以证明其大小至多为（2 +o（1））·2ν/ν。✷例6.2考虑以下情况：使用普通的ROBDD，没有带符号的数字，r = 2，并表示双精度型的64位，而不考虑它们的解释，我们需要n = 6个变量来表示位的位置。这导致了32n+k/（n+k）n个节点到2k个不同的双值的上界，这是32n/（n+k）个节点/值的比率。如果n= 6，存储惩罚因子为2（一个节点至少大于一个double），这意味着我们需要k>2 3 26 400，直到比率降到1以下。因此，为了确保使用比普通表示更少的存储器，我们将需要大小为#I>2400的索引集I，其太大以至于它没有任何实际意义。上面引理的（b）部分的证明必须考虑标记有相同变量的节点之间可能的独立性，从而导致项N（ν j）。由于这种独立性并不总是给定的，我们可能会得到更小的上界结构化的情况下，如编码一个真正的功能到一个r-sdBDD。在这里，我们将考虑最简单的情况，我们能够证明更低的上限。我们首先定义正则r-sdBDDsAf，n.k逼近函数f：设D r<$D r是非冗余数字子集{d-[r+1||0≤ d 0也是如此：对于l可能出现的r个数字最多导致r+ 1个子区间，在l处给出相同的数字。所以l的2ν值将r分成（至多）2ν（r+ 1）个子区间，这些子区间唯一地确定一个数字序列。因此，至多存在2ν（r+ 1）个不同的数字序列.✷152≤≤··≈7实验结果如引言所述，我们正在评估r-sdBDD的原型实现它基于科罗拉多大学博尔德分校的Fabio Somenzi的BDD包cudd-2.3.1到目前为止，它只能执行加法，减法和乘法（与学校男孩的方法）。我们使用这个原型来计算r-sdBDD A f，[log2k]的大小|，k对于函数f（x）= x和f（x）= x2，以及对于10 k 26，即对于表 有大约6700万个位置，每个位置的精度大约为k位，即n log k。实验验证了引理6.4，在f（x）=x的情况下，其大小约为k2k/2nodes。 对于x2wgetasizeofaboutk20. 8·k，但我们不能证明在这种情况下确实存在O（2o（1）·k）的界K下表绘制了A f，[log2k]的大小|，k对于2个索引与k，在对数标度，因此引理6.4的结果显示为斜率为0.5的几乎线性函数：1e+081e+071e+0610000010000100010010 12 14 16 18 20 22 24 268致谢原型实现基于科罗拉多大学博尔德分校的FabioSomenzi的BDD包cudd-2.3.1。在最初的版本中，使用Graphviz非常有帮助，这是AT T Research和Lucent Bell Labs的图形绘制程序。这两个软件包都可以在互联网上免费获得。rsdBDD大小，函数f（x）=x rsdBDD大小，函数f（x）=x*x生长：3*k*2^（k/2）生长：0.3*k^2*2^（4k/5）增长：2^k153引用[1] H. R. Andersen ， An introduction to Binary Decision Diagrams ， LectureNotes available in the internet ， URL ： www.it-c.dk/people/hra/notes-index.html[2] A. Avizienis，Signed-Digit Number Representations for Fast Parallel Arithmetic，电子计算机学报。EC-10（1961）389-400[3] G. Ciardo，A.S. Miner，A data structure for the efficient Kronecker solution ofGSPN ， Proc. 8th Int. Workshop on Petri Net and Performance Models（PNPM'99），8-10 October 1999，Zaragoza，Spain，pp. 二十二至三十一[4] E.M.Clarke，M.藤田，P.C.McGeers，K.McMillan，J.C.Y.Yang，多端二元决策图：一种有效的矩阵表示数据结构IWLS'93。一九九三年五月[5] N.Th. Mu？ller，R_al函数和R_al数的次多项式复形类，Proc.第13届ICALP，计算机科学讲义226（施普林格，柏林）第284-293页（1986）[6] N.Th. Müller，T泰勒级数的统一计算复杂性，Pr oc。第14届ICALP，计算机科学讲义267（施普林格，柏林）第435-444（1987）[7] N.Th.Müller，TheiRRAM：ExactArithmeticinC++，ComputabilityandComplexity in Analysis-CCA 2000 ， Lecture Notes inComputer Science2064（Springer，Berlin，2001）222-252[8] B. Parhami，牛津大学出版社，纽约，2000年[9] M.张文，随机转移系统的BDD扩展，北京大学学报，1997年[10] I.王文，[11] K. Weihrauch，导论》，施普林格出版社，柏林，2000年
我的内容管理
展开
