This is something I've been wondering for years. Software like Mathematica is great at manipulating expressions into simplified, factorized, and other forms. I'm wondering if there's a way, theoretically and/or practically, to find the form that has the fewest operations. The next step would be to prefer operations that are faster (ie. multiply instead of divide). Lastly, to find a form that maximizes extraction of repetitive subexpressions, so that the subexpressions can be evaluated once and substituted for potentially significant performance gains. Has any research been done in this area? Thanks.
This doesn't completely answer your question, but you ask if research has been done on this.
This is an area called Symbolic Algebra. I'm sure there are many such research groups, but here is one:
They're the group at Waterloo which developed the Maple software (similar to Mathematica).
That sounds like the principles of compilers. They're designed to do such things. On the other hand, computational science is the field that studies optimizations for algorithms in order to do less operations, minimize rounding errors and so on.
Check out any compiler book, they give an overview of what a compiler does. Just keep in mind that the simplistic algorithms described (and the not too complex cases they handle) are far from what is today's state of the art.
"Optimizing" expressions (or any code) is most of the time counter-productive: It takes up your (valuable) time doing the changes, testing them, and keeping them up to date when the program changes (and you know you won't understand a line of the program in a week's time, so an afternoon goes by while you wrap your head around it next time), all to shave off a bit of (inexpensive) computer time. If it really reduces execution time... today's compilers are much better at doing the kinds of changes you propose than you will ever be, such modifications are rarely applicable (most expresisons are very simple), and finally experience has shown time and again that programmers are terrible at guessing what parts of their programs are worth trying to make faster.
A google search of computer algebra optimization brings up a few hits that look promising. I can vouch for the effectiveness of this approach in reducing the number of operations required for matrix multiplication where:
- there are complex patterns in the matrix
- the cost of the factorization can be amortized over many subsequent multiplications.
What I did was quite simple so I was able to write the CAS myself. If you do it yourself a compact language such as Scala is helpful. More complicated problems would probably be better solved using a properly designed CAS. Many are able to generate code in more conventional computer languages for numerical execution.
Of course compilers do a little of this already, but there are lots of optimisations that they miss in large problems.
On a related point, I've often wondered if an approach like this could be used in query optimization, using set theory.