Ok, I've added CSE of Add and Mul arguments (only commutative terms): http://nbviewer.ipython.org/5986996
It runs faster compared to current sympy.cse, even more if applying it to large expressions. However, it still lacks a lot of features, which I'll try to address using sympy.cse unit tests. On Wednesday, July 3, 2013 2:52:13 PM UTC+1, Cristóvão Sousa wrote: > > 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.
