Ames Laboratory, Department of Energy, ISU, Ames, Iowa

Aggressive Pruning Rules

As the size of the search tree is exponential both in the number of variables and the number of operations, we need as many pruning rules as possible to be able to tackle interesting problems in reasonable time. Due to this, we added some pruning rules that seem to be intuitively appealing, without the guarantee that they eliminate only unpromising subtrees. These rules greatly assist in finding clever solutions but cannot be used to prove the nonexistence of any methods with a given operation budget:

1. Eliminate expressions with degree higher than the highest degree among goal expressions.
2. If the goal expressions are all homogeneous, do not allow expressions with terms of different degree.
3. If the goal expressions do not contain terms of the form n expression, where nis an integer, |n| > 1 and expression is a product of input variables, then we can also exclude all operations that result in such terms.

   This set of pruning rules, along with the conservative pruning rules, reduces the number of possibilities for the a² - b² search space from 15552 to a much more manageable 24 expressions. The savings are more dramatic for larger search trees, of course. The resulting search tree for the computation of a² - b² is shown in figure 7.

   

   FIGURE 7. Aggressively pruned search tree for a² - b²

   A few more pruning rules were found useful in dealing with goal expressions denoting the product of two mathematical entities like complex numbers, vectors and matrices. None of the goal expressions for such a product contains a term with two variables drawn from the same operand and none of the known shortcuts contains any intermediate expressions with such terms.

   We define the structure of a term to be the sequence of operand names from which the variables forming the term are drawn. For example, with respect to the complex product (a + ib) (c + id), the term bc has the structure (exp1, exp2), where exp1 and exp2 refer to the first and the second operand respectively. The following pruning rules are based on the structures of expressions. Due to these pruning rules, each expression is made of terms of the same structure and the structure of any term can be taken as the structure of the entire expression.

4. , operations are allowed only on operands of the same structure.
   

5. is allowed only on operands of different structures.