Hi Jim, thanks for your suggestion. It's along the right lines, and I wasn't aware of this idea. One issue is that the Horner form of a multivariate polynomial depends on the order of the variables, and this introduces severe inefficiencies for the types of expressions I have.
My approach, which is nearly working, is to define a complexity function that counts the number of multiplications and adds it to the number of exponentiations. For technical reasons, the only exponents that can appear in the expressions are 2, so these "look like" multiplications in terms of my goal, which is to minimize the number of multiplications.
One weird thing is that FullSimplify does seem to find the global minimum for my custom complexity function when applied to shorter expressions, but for larger expressions it doesn't come close. What's funny is that if I manually improve the expression in terms of the complexity function, FullSimplify applied to the result returns the manual solution. In other words, it seems that the search algorithm in FullSimplify is not working well. Is there any way to improve its performance?
For reference, the expressions are functions of 39 real variables, and the fully expanded polynomial is a sum over about 100 terms.
