Perform some simple preprocessing of contractions

dgasmith / opt_einsum

⚡️Optimizing einsum functions in NumPy, Tensorflow, Dask, and more with contraction order optimization.

https://dgasmith.github.io/opt_einsum/

MIT License

863 stars 68 forks source link

Perform some simple preprocessing of contractions #114

Open jcmgray opened 5 years ago

jcmgray commented 5 years ago

It might be sensible (#99 and #112) for opt_einsum to perform some simple universal pre-processing of contractions before sending them to the actual path optimizers. Including:

single index reduction e.g. abc->ab where the index c appears on no other terms
hadamard de-duplication e.g. ab,ab->ab

Some things to think about

[ ] make the pre-processing optional (but default on?)
[ ] might be useful to first have some generic way to combine bits of two paths
[ ] include other more complex but sensible steps - e.g. contract disjoint subgraphs separately?

dgasmith commented 5 years ago

This does need to be optional and I would think a default off state to retain current functionality. I am a bit hesitant to make changes to current algorithms without discussing more with downstream programs.

Disjoint subgraphs seems like it would influence each algorithm differently and likely not able to be generalized. Similar to the path combination, each algorithm uses different internal structures at the moment and likely needs to remain that way for performance.

dgasmith commented 5 years ago

@jcmgray I might try this today, are you working on any pieces currently?

jcmgray commented 5 years ago

I'm adding a few tweaks to the 'dp' algorithm, (with an eye on it replacing the current 'optimal' implementation) but that's all pretty much self contained!