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

Problem Specification

The problem can be defined as follows:

Given:

• A set of variables
• a budget of M multiplications and A additions
• and a set of goal expressions

Find: A sequence of (exp1 op exp2) triples where exp1 and exp2 are selected from either the set of variables or previously computed expressions, and op is chosen from the remaining multiplications or additions that compute the goal expressions, and that minimize the total number of operations or the number of operations of a particular type.

We are interested in minimizing the number of operations of a particular type because the relative cost of the operation types is different in general. For example, in Strassen's matrix product algorithm, the variables involved could themselves be matrices, and matrix products are costlier than matrix sums. Any algorithm for finding the product of two k k matrices in M multiplications can be used recursively to find the product of two n n matrices (n k) in O(n^{log_k M}) time [1,20]. For such a problem, we are obviously interested in minimizing the number of multiplications, even at the cost of increasing the total number of addition operations.

For the class of problems addressed in this paper, addition (), subtraction (), and multiplication () operations are sufficient. Addition and multiplication are commutative, while subtraction is not. For the purposes of uniformity, we introduce a notation "reverse subtraction" (), with the associated meaning that exp1 exp2 is the same as exp1 exp2. With this, we can impose an ordering on exp1 and exp2 and explore only cases with exp1 < exp2 without omission. Also, we use the term "add" to denote any of addition/subtraction/reverse subtraction. Throughout the paper, we assume that operation cost is data independent. We also use the term "product" to refer to multiplication of entities like complex numbers and matrices and reserve the term "multiplication" for real numbers.