4
$\begingroup$

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.

$\endgroup$
  • $\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$ – Brent May 17 '13 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$ – jmite May 17 '13 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$ – vonbrand May 17 '13 at 20:33
2
$\begingroup$

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:

https://www.scg.uwaterloo.ca/

They're the group at Waterloo which developed the Maple software (similar to Mathematica).

$\endgroup$
1
$\begingroup$

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.

http://en.wikipedia.org/wiki/Computational_science

$\endgroup$
  • $\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$ – Brent May 17 '13 at 18:56
  • $\begingroup$ To me, computational science is more about numeric solutions than symbolic manipulation. $\endgroup$ – jmite May 17 '13 at 19:14
  • $\begingroup$ I thought it was related to computational science at the beginning when the question lacked of any example :) $\endgroup$ – Alejandro Sazo May 17 '13 at 19:16
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.