Solution 1: $ n$ set operations

The following approach is faster, as it does not involve individual terms, but set operations

def evaluate(f,m):
   while not f.constant():
       nav=f.navigation()
       i=nav.value()
       v=Variable(i)
       c=m[v]
       if c==0:
           #terms with x evaluate to zero
           f=Polynomial(nav.thenBranch())
       else:
           #c==1
           f=Polynomial(nav.thenBranch())+Polynomial(nav.elseBranch())
       return f
For example, the call
evaluate(x(1)+x(2),{x(1).index():1,x(2).index():0})
results in 1.

We deal here with navigators, which is dangerous, because they do not increase the internal reference count on the represented polynomial substructure. So, one has to ensure, that $ f$ is still valid, as long as we use a navigator on $ f$ . But it will show its value on optimized code (e.g. PyRex), where it causes less overhead. A second point, why it is desirable to use navigators is, that their thenBranch- and elseBranch-methods immediately return (without further calculations) the results of the subset0 and subset1-functions, when the latter are called together with the top variable of the diagram $ f$ . In this example, this is the crucial point in terms of performance. But, since we already call the polynomial construction on the branches, reference counting of the corresponding subpolynomials is done anyway.

This is quite fast, but suboptimal, because only the inner functions (additions) use caching. Furthermore, it contradicts the usual ZDD recursion and generates complex intermediate results.

2009-09-10