Minimize number of arithmetic operations

[Pfaeff]

Hi there,

I just started using sympy for a small code optimization problem that I have. 

Let's say I have a bunch of simple, linear expressions (I made these up just as an example):

2 * a + (b * c) + 4 * (a + 3 * d)

(b * c) + 2 * (c + 3 * d)

...

I now want to identify common operations in this set of expressions and combine them in order to minimize the number of arithmetic operations in my program:

y = b * c

z = 3 * d

2 * a + y + 4 * (a + z)

y + 2 * (c + z)

Does sympy have a built-in way to do this? If it doesn't, how would I go about it? My idea was to traverse all expression trees and find the longest common expressions or something.

Thanks in advance.

Greetings,

Pfaeff

[Arif Ahmed]

You can use the common subexpression (cse) function in SymPy to perform this task.

>> from sympy import *
>> from sympy.abc import *
>>> k = 2*a + b*c + 4*(a + 3*d)
>>> l = (b*c) + 2*(c + 3*d)
>>> cse([k, l])
([(x0, b*c + d)], [6*a + 11*d + x0, 2*c + 5*d + x0])


The result got by SymPy is not exactly the same as the one you posted but is similar in the number of multiplications and additions.

[Pfaeff]

That's exactly what I was looking for. Thank you very much!

[Pfaeff]

The cse create some expressions that are just aliases of existing symbols. How can I prevent that?

e.g. (x5, x1), (x7, -x5)

[Arif Ahmed]

That might be an issue with the current cse algorithm.
I have recently applied to SymPy for a summer project to improve it : https://docs.google.com/document/d/18pLah093CgClXM9i1LTPfkBjBvFDGhqQrR5TkkG8F2E/edit#
Such an issue should not crop up with this different algorithm.

[Pfaeff]

That looks promising. Is there a workaround for the time being?

[Arif Ahmed]

Not that I know of.
You could post your query on the SymPy gitter channel as well : https://gitter.im/sympy/sympy

[Aaron Meurer]

Can you open an issue with the full expression that resulted in this.
cse() should never give trivial assignments like (x5, x1).

Aaron Meurer

> --
> 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 sympy+un...@googlegroups.com.
> To post to this group, send email to sy...@googlegroups.com.
> Visit this group at https://groups.google.com/group/sympy.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/sympy/e85e2684-10ff-4e05-be40-651570b24d85%40googlegroups.com.
>
> For more options, visit https://groups.google.com/d/optout.

[Pfaeff]

It seems that this only happens when the symbol is a matrix element. It will then sometimes (not always) get assigned another alias.

[Richard Fateman]

for what it is worth

(1) rearranging expressions does not guaranteed that they

will evaluate to the same values, given floating-point data.

(2) this ad hoc searching for common subexpressions is

not going to extract the best way of evaluating (say)

polynomials that can be factored, or can be evaluated

by some divide-and-conquer halving.  Or matrix

expressions with fast operations. Or FFT-related speedups.

The biggest payoffs traditionally in compiler technology

(look this stuff up if you don't know it) is in moving

expression evaluation outside of loops, or even improving

the evaluation of the loop index.

RJF