search

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

added dp documentation #106

Closed mrader1248 closed 5 years ago

mrader1248 commented 5 years ago

Description

Added documentation for the dynamic programming (DP) path optimizer.

jcmgray commented 5 years ago

Thanks for adding these! All looks good to me and I think I finally understand the internals. The only remaining thing to do is to add a reference in the index doc (line ~160), then it will appear on readthedocs etc.

codecov[bot] commented 5 years ago

Codecov Report

:exclamation: No coverage uploaded for pull request base (master@c17dcea). Click here to learn what that means. The diff coverage is n/a.

jcmgray commented 5 years ago

Thanks again for adding this optimizer - will be very useful. For future reference, does 'asymptotically' optimal refer to increasing bond sizes?

mrader1248 commented 5 years ago

Thank you as well for your support.

Exactly, 'asymptotically optimal' refers to increasing dimensions. Consider for example the equation "a,b,abc->c" (and let's call the dimensions da, db, and dc. The computational complexity of this would be O(da*db*dc + da*db), O(da*db*dc + da*dc), or O(da*db*dc + db*dc), depending on which contraction you perform first. For the one with + da*db one has to compute an other product first, which will never be done by the DP approach. So, if for example da*db < da*dc < db*dc, it would be better to compute the outer product first, but asymptotically all these three contractions paths are equal.