8
$\begingroup$

Given a binary expresion tree, with addition and multiplication operations, how can we optimize it's evaluation?

Can we learn from matrix chain multiplication? A generalization of matrix chain multiplication is defined as:

Given a linear sequence of objects, an associative binary operation on those objects, and a way to compute the cost of performing that operation on any two given objects (as well as all partial results), compute the minimum cost way to group the objects to apply the operation over the sequence.

What happens if we put two binary operators? Can the algorithm for Matrix chain multiplication be further generalized (or how can we otherwise solve this problem) to two binary operators in a binary expresion tree, given the cost functions of these operations? In particular, multiplication and addition, which complicates things further by allowing distribution. Also, does it matter that mind that some of the numbers can be negative, allowing reduction in size of intermediate results (see Overflow safe summation)?

Also, how does this relate to Graph Reduction?

I also remember learning about database query optimization which seemed to do something similar to determine how early to execute particular joins to keep the intermediate values smaller.

Improve this question
$\endgroup$
5
  • $\begingroup$ This question confuses me a lot. For the associative operation (matrix chain) the tree of computations is unknown, but any tree gives the same answer. Only a cost can be defined on the tree, and optimized. With two operations I see not much room for changing the tree without changing the outcome of the computation. Be more precise please. $\endgroup$ – Hendrik Jan Nov 28 '12 at 23:09
  • $\begingroup$ @HendrikJan Example: $(a+b+c+d)\cdot (e\cdot f\cdot (g+h)) = (((a+c)\cdot e) + ((b+d)\cdot e)) \cdot ((f\cdot g)+(f\cdot h))$. So the LHS can be rewritten as binary operations on the right. It can be rewritten in many such ways. The question asks what would be a nice algorithm to discover the optimal evaluation order. Am I misunderstanding your comment? $\endgroup$ – Realz Slaw Nov 28 '12 at 23:40
  • $\begingroup$ OK. Thanks, that makes me think. Seems hard, and very general. For example, note that in the matrix multiplication application the possibilities are limited by the fact that we do not (cannot) assume commutativity of the operation. We are only limited in putting brackets in the single line of matrices. $\endgroup$ – Hendrik Jan Nov 29 '12 at 0:07
  • $\begingroup$ Think of it in the binary tree format, it will be easier to reason with perhaps. But yes, the question is exactly about generalizing the matrix chain multiplication algorithm further, and it does seem hard. If you read the wikipedia article on chain multiplication though, it does say you can generalize it to any binary expression tree with a single operator essentially. But you are right, this generalization will not re-order them, only regroups them. I also mentioned distributive property across addition, which seems like an additional monkey wrench. My hopes for an answer continue to fall :( $\endgroup$ – Realz Slaw Nov 29 '12 at 0:13
  • $\begingroup$ I do have a less general question that happens to be a specialization of this that I will follow up with soon though. $\endgroup$ – Realz Slaw Nov 29 '12 at 0:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.