Forwarded from PyDy mailing list, https://groups.google.com/forum/#!topic/pydy/PjZ9SP8PYDA .
Hi, I'm posting here because of one of GSoC 2013 ideas, "Efficient Code Generation". You stated that "Common subexpression elimination (cse) takes a long time (>1 hour) to run on systems of equations that are derived in a very short period of time (< 1 minute). This needs to be improved." [https://pydy.org/gsoc_2013_ideas#efficient_code_generation] Indeed, I've verified that myself on my work on SymPyBotics (https://github.com/cdsousa/sympybotics), a tool I'm developing to help me on my PhD studies. So, I've developed a kind of CSE, faster than SymPy CSE though less general and with some quirks. Such CSE functionality is implemented in SymCode package (https://github.com/cdsousa/symcode). Be aware that both SymPyBotics and SymCode are badly documented and probably reimplement some functionalities which could be taken from SymPy/PyDy (and I probably implement them in worse ways :) The cse core function is "fast_cse()" which can be found in symcode/subexprs.py (https://github.com/cdsousa/symcode/blob/master/symcode/subexprs.py.) (It uses Subexprs class, which can be used alone to store intermediate variables in recursive computations). I've profiled SymPy cse and noticed that the main time consumption is due to "count" and "subs" functions, so I tried a different approach. First, fast_cse function reversely parses the expression tree and recreate each unique operation with non-atom arguments substituted by temporary symbols (this is the "collect" phase). Each unique operation is stored on an "unique_op:tmp_symbol" dictionary. For example, a + b*c + cos(b*c) is transformed into t2 while the dictionary holds a + t0 + t1 : t2 cos(t0) : t1 b * c : t0 Additional, match of multiple argument Mul and Add operations is made, in a similar way to SymPy cse, although argument commutativity is always assumed. Then, in the "get" phase, the expression tree is recreated from the dictionary while temporary "used more than once" symbols are maintained. The example output will be ( [(t0, b*c)], a + t0 + cos(t0) ) This is much faster than SymPy CSE although output is generally different. Also, it still doesn't work with "iterable" arguments, and, as said, non-commutativity is not respected . I would love to have time to work on this, or to work on SymPy CSE optimization directly, but I'm currently in work overload. Nevertheless, I'm showing you this since some ideas can be useful. Best regards, Cristóvão Sousa -- You received this message because you are subscribed to the Google Groups "sympy" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at http://groups.google.com/group/sympy. For more options, visit https://groups.google.com/groups/opt_out.
