3
$\begingroup$

Say I have an expression involving adds, subtractions, and multiplications. I know that it is safe to assume commutativity, associativity, distributivity, etc., and would like to automatically generate a simpler expression which involves fewer operations. All interesting variants of this problem are NP complete, but are there existing tools or algorithms which work well in practice?

As a baseline, currently I am using Mathematica's FullSimplify command and then running common subexpression elimination on the result. Unfortunately, the result isn't even minimal (it misses obvious distributive law simplifications), and it'd be nicer to have a tool which works on DAGs natively.

Improve this question
$\endgroup$
1
$\begingroup$

This is a classical problem compiler builders face in trying to optimize code. For example, Common Subexpression Elimination (CSE) is one way. I would suggest you look into the books that describe compiler building.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Yep, I mentioned CSE in the question. $\endgroup$ – Geoffrey Irving Aug 5 '13 at 17:38
  • $\begingroup$ Right, I missed that. But the point remains true -- a book on compiler engineering would be the best source in my mind. I'd recommend the Dragon Book, but then I'd reveal my age by doing so... $\endgroup$ – Wolfgang Bangerth Aug 5 '13 at 20:07
  • $\begingroup$ I've read the Dragon Book, and implemented some of the algorithms in the past, but I don't think they go as far as I'd like. A closer analog is the custom simplification work done by FFTW, but that's limited to linear expressions. One issue is that most high performance complex expression evaluation is floating point, which standard compilers aren't allowed to mess with. $\endgroup$ – Geoffrey Irving Aug 6 '13 at 0:18

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.