Looking for a way to continue cse with prior set of subexpressions

[Jason Moore]

Hi,

I'd like to be able to do something like this:

expr = ....

com_sub_exprs, simplified_expr = cse(expr)

new_expr = do_operations_on(simplified_expr)

com_sub_exprs, simpflied_new_expr = cse(new_expr, start_with=com_sub_exprs)

This would let the cse() of new_expr use the existing set of sub expressions as the starting set and add more as needed, as those subexpression may exist in new_expr.

Is there a way to do this with existing functionality or would I need to add this "start_with" piece to cse() as a new feature?

Thanks,

Jason

moorepants.info
+01 530-601-9791

[Aaron Meurer]

Is it just a question of replacing the old cse symbols in the new
expression before calling cse, then merging the results? I think that
wouldn't be hard, though probably complicated enough that direct
support could be added.


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 view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CAP7f1AgCh2yqarPodb-EhZ8X_Gp7SxuscDo57jSkLt371y9swQ%40mail.gmail.com.

[Jason Moore]

I could do that, but for very long expressions this means cse has to do the work twice. This can be time consuming for long expressions.

Jason

moorepants.info
+01 530-601-9791

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CAKgW%3D6J3mtqLU%3DG6y%2BzrAX_oq8DLTqPfTj%2Bp3_cP36Ub_qk8%3DA%40mail.gmail.com.

[Aaron Meurer]

I'm not clear, what work would it have to do twice?

Aaron Meurer

> To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CAP7f1AjH4ncRALDnK2c%3DZW%2BTGeXcQDHa1M-XDSHur3QqvTDV2A%40mail.gmail.com.

[Jason Moore]

I think you meant to do this:

expr = ....

com_sub_exprs, simplified_expr = cse(expr)

new_expr = do_operations_on(simplified_expr)

com_sub_exprs, simpflied_new_expr = cse(new_expr.subs(dict(com_sub_exprs))

If so, seems like you have to cse the same set of sub expressions twice.

moorepants.info
+01 530-601-9791

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CAKgW%3D6LSobhOPTxEZWjrknJ%3DwXe7ggRBb50MN6epJvOOSNFkog%40mail.gmail.com.

[Jason Moore]

This is possible already:

expr = ....

com_sub_exprs1, simplified_expr = cse(expr)

new_expr = do_operations_on(simplified_expr)

com_sub_exprs2, simpflied_new_expr = cse(new_expr)

com_sub_exprs = com_sub_exprs1 + com_sub_exprs2

But I don't think you've necessary got the smallest number of common sub expressions with that method.

Jason

moorepants.info
+01 530-601-9791

[Jason Moore]

This wouldn't work, as it needs to be done recursively:

com_sub_exprs, simpflied_new_expr = cse(new_expr.subs(dict(com_sub_exprs))

But the idea is reconstructing the new_expr fully and then cse'ing again.

Jason

moorepants.info
+01 530-601-9791

[Aaron Meurer]

On Wed, Nov 4, 2020 at 1:57 PM Jason Moore <moore...@gmail.com> wrote:
>
> I think you meant to do this:
>
> expr = ....
> com_sub_exprs, simplified_expr = cse(expr)
> new_expr = do_operations_on(simplified_expr)
> com_sub_exprs, simpflied_new_expr = cse(new_expr.subs(dict(com_sub_exprs))
>
> If so, seems like you have to cse the same set of sub expressions twice.

Yes, except com_sub_exprs has to be reversed first. I'm still not sure
about your duplicate work comment. The same subexpresisons would be
replaced by the subs, so the second cse would only see the CSE'd
replacement symbol.

But I think there are some technicalities that make this more
complicated than this naive version:

- cse does some preprocessing that makes subexpressions easier to
find. It may not be possible to reverse substitute successfully unless
these are done. Actually there may be cases where is still doesn't
work, because the subs() behavior for replacing expressions isn't
guaranteed.
- The subs dict has to be reversed.
- If it did work, merging the two cses would require renumbering the symbols.

So I think it is worth adding this directly to cse. It's possible that
this can be done at a more internal point in the cse algorithm to make
it more robust.

Aaron Meurer

> To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CAP7f1Ah4dWVcQyWuscnXkb0H6MC51MReGR-OBpPmUODS_AdDPA%40mail.gmail.com.