Intersection of Zero-Suppressed BDD - Implementing Polynomials Using ZDD

Question

I am trying to implement one-dimensional polynomials using ZDD, as suggested in a comment on another question .

I read an article by S. Minato (you can download here ), but I don’t understand how to implement operations on these ZDDs.

The idea in this article is that polynomials can be represented using x^(2^i) as variables. For example, x^5 + x^3 + x can be rewritten as x^4x^1 + x^2x^1 + x^1 , if you create nodes for each variable x^(2^i) and connect to the variables "1 edge "that are multiplied together and with the" 0-edge "variables that are added together you can easily get a graph representing this polynomial. ZDDs are charts of this type that ensure that a certain condition is fulfilled on the chart (for more information see the Minato and wikipedia article on the BDD page )

Coefficients can be represented in a similar way using sums of degrees 2 (for example, 5 = 2^2 + 2^0 , etc. For every 2^i there is a variable, and the nodes are connected with 1- and 0-edges in the same way).

Now my problem is the algorithm for adding two ZDDs. The algorithm seems pretty simple:

If F and G (ZDD) do not have common combinations, the addition of (F + G) can be completed by merging them. When they contain some general ones, we calculate the following formulas: (F + G) = S + (Cx2), where C = F ∩ G, S = (FUG) \ C. By repeating this process, the common combinations are eventually exhausted, and the procedure is completed.

The problem is this: how can I find “C” and “S” effectively?

The author provides code for multiplication, but the code is actually trivial after implementing the previous algorithms. And since these algorithms are not provided, then multiplication is "useless."

Also, the concept of “merging" ZDD is not well explained, although, given the fact that the order of the variables must be consistent, there is only one way to combine the graphs together, and the rules for maintaining this order are probably quite simple (I have not formalized them yet, but I have a general idea of ​​what it is).

Answer 1

With "merge" there Minato means union (algorithm) . You can also see this from an example:

 4 * y = { { 2^2, y } } x = { { x } } 4 * y + x = { { 2^2, y }, { x } } 

The idea is that internal sets are products, and the entire ZDD is the sum of these products, so if you are just OR (aka union or merge) in some other sets, they are effectively added.

The complete summation algorithm is actually simple (A xor B) + 2 * (A and B) (recursively), which is equivalent to the familiar bitwise addition algorithm, but xor was written as (A or B) without (A and B) .

It also makes it obvious why it’s easy to take the union in order when there are no common combinations — if A and B empty, A xor B matches A or B , and the “carry” is zero.

The algorithms for OR, AND, XOR, and BUTNOT are explained in detail in the section "Software Scope" 4, section 7.1.4 (the answer to question 199 matters). The general idea for everyone is that they consider two subgraphs that represent all sets with the variable v and all sets without the variable v separately (which are trivially found if v is the highest variable in one or both arguments, both low and and high, or the input itself), and then combining the result.

 Union(F, G) = if (F = ∅) return G if (G = ∅) return F if (F = G) return F if (cache contains "F ∪ G" or "G ∪ F") return cached value if (Fv = Gv) result = MakeNode(Fv, F.lo ∪ G.lo, F.hi ∪ G.hi) if (Fv > Gv) result = MakeNode(Gv, F ∪ G.lo, G.hi) if (Fv < Gv) result = MakeNode(Fv, F.lo ∪ G, F.hi) cache result as "F ∪ G" return result Intersect(F, G) = if (F = ∅ or G = ∅) return ∅ if (F = G) return F if (cache contains "F ∩ G" or "G ∩ F") return cached value if (Fv = Gv) result = MakeNode(Fv, F.lo ∩ G.lo, F.hi ∩ G.hi) if (Fv > Gv) result = F ∩ G.lo if (Fv < Gv) result = F.lo ∩ G cache result as "F ∩ G" return result