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.
$\begingroup$
$\endgroup$
3
-
$\begingroup$ I know compilers do a lot of simple stuff, like constant folding and constant propagation. I'm talking about more complex transformations. A compiler isn't going to convert something like "return cos^2(u) - sin^2(u) + cos(2u) * v" to "temp = cos(2u); return temp * (v + 1)" $\endgroup$– BrentMay 17, 2013 at 18:42
-
$\begingroup$ My suspicion is that many of these problems are either NP-Hard or flat-out undecidable. That said, I don't have proof of this, and even if they are, there's a good chance that there are lots of real word approximations which work quite nicely. $\endgroup$– jmiteMay 17, 2013 at 19:12
-
3$\begingroup$ @Brent, you'd be in for a big surprise seeing the kinds of code reorganizations a decent compiler does nowadays. $\endgroup$– vonbrandMay 17, 2013 at 20:33
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
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).
$\begingroup$
$\endgroup$
3
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.
answered May 17, 2013 at 18:34
-
$\begingroup$ I've added a comment to the original question with an example. I skimmed the Computational Science article (a topic that I'm somewhat familiar with), but the only thing I could find relating to optimizations was "mathematical optimization." I guess that is loosely the same problem, but it's rather nonspecific to optimization of a sequence of operations. I suspect that the conventional methods for solving optimization problems don't really apply to optimization done by compilers. Please correct me if I'm wrong, though. $\endgroup$– BrentMay 17, 2013 at 18:56
-
$\begingroup$ To me, computational science is more about numeric solutions than symbolic manipulation. $\endgroup$– jmiteMay 17, 2013 at 19:14
-
$\begingroup$ I thought it was related to computational science at the beginning when the question lacked of any example :) $\endgroup$ May 17, 2013 at 19:16
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
