Re: [Loopy] Finding common subexpressions
by Fernando, Isuru Dilanka
To turn off simplification in sympy you can do,
from sympy.core.evaluate import evaluate
# run your code here
> However, unevaluated expressions raise errors in the cse algorithm!!!
If the error you mention is "ValueError: repeated commutative arguments:" then that's a sanity check that should be turned off when running sympy's cse and is a one line fix. "c, nc = m.args_cnc(cset=True)" -> "c, nc = m.args_cnc(cset=True, warn=False)"
Also, sumpy has a faster cse implementation for large expressions written by Matt. You might want to try that. This doesn't have that problem. (Because sumpy skips that part of the code assuming there are no non-commutative arguments)
From: Loopy [loopy-bounces(a)tiker.net] on behalf of Dominic Kempf [dominic.r.kempf(a)gmail.com]
Sent: Thursday, September 07, 2017 9:40 AM
Subject: [Loopy] Finding common subexpressions
Dear loopy list,
Loopy currently is perfectly able to implement common subexpression elimination if the CSE is marked with a substitution rule. I have to target a different problem though: How can common subexpressions be identified in an automated way. Implementing such a thing on your own is a hard task and might easily turn into writing a fullblown CAS. I totally want to avoid that. So I had a look at existing alternatives and made some experiences, that I would like to share here:
Using sympy for CSE:
* there is a function sympy.cse which identifies simple CSEs.
* The pymbolic <->sympy interop layer needed some tweaks to accept all my kernels. These were (in order of niceness of the fix)
* Subscript nodes were not previously translated (fixed with sympy.tensor.indexed.Indexed)
* Modulo operation did not map correctly (fixed with handlers for sympy.Mod)
* If statements from pymbolic were mapped through evaluation mapper, which leads to highly undesired behaviour, like
If(Comparison(Variable("x"), "==", Variable("y")), 0, 1) being mapped to 1, because x and y are not the same string.
(fixed with sympy.Piecewise and sympy.Eq, Lt, Gt etc.)
* FloorDiv nodes have no sympy equivalent, but are implemented by applying a floor function to the division result (fixed by ugly pattern matching)
* loopy.FunctionIdentifier objects are unhandled (fixed by keeping a dict and restoring them on back transformation)
* Sympy CSE can be supplemented with a list of homebrewed optimization passes
* Sympy applies aggressive simplification, which in some test cases even *DESTROYS EXISTING CSES*.
Turning off this simplification only seems possible like in this example: sympy.Mul(expr, expr, evaluate=False)
However, unevaluated expressions raise errors in the cse algorithm!!!
=> I now totally doubt that I want to use sympy for CSE finding
=> I appreciate and understand how pymbolic came into existence
Using maxima for CSE:
* maxima has an optimize function, which returns a list of CSEs and a simplified expression rewritten in terms of it
* maxima also provides lots of possibilities for custom optimization
* maxima also simplifies aggressively, but this can be turned off with "simp:false"
* The maxima parser shipped by pymbolic would need to be enhanced to be able to parse the output of optimize
* I do not know yet how many pymbolic nodes do not map properly or map falsely into maxima
Right now, I think I will invest a bit more time into finding CSEs with maxima.
There are a few questions that I have to all of you:
* Are there are other (python) packages which may be worth looking into for my purpose?
* Am I missing some sympy option to make it smart?
* Are there experiences with the pymbolic <-> maxima interop layer?
I am grateful for any input into this topic.