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.