Ok, I think it makes sense to continue the posts from https://groups.google.com/forum/#!topic/pydy/PjZ9SP8PYDA here.
I've implement a fast_cse() with the ideas I had. code: https://gist.github.com/cdsousa/a3dd16fea7c0bd27f07a ipynb example: https://gist.github.com/cdsousa/e404a692e268e8df18de It is still incomplete (see todo at top of code). Compared to current sympy cse, my routine does not revisit the whole subexpression tree if it has already been seen, so it can set 'to_eliminate' top duplicated subexpressions only, thus there is no need to '_remove_singletons()'. Also, instead of using 'subs()' on the expressions, it recreates the whole tree replacing operation 'args' that are 'to_eliminate' with symbols (I will look inside subs() to better implement this). I'll keep working. Cristóvão 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/#!topi<https://groups.google.com/forum/#!topic/pydy/PjZ9SP8PYDA>Forwarded > > from PyDy mailing list, > https://groups.google.com/forum/#!topic/pydy/PjZ9SP8PYDA . > c/pydy/PjZ9SP8PYDA<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.
