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

Faster 'dp' for asymptotic contractions #115

Open jcmgray opened 5 years ago

jcmgray commented 5 years ago

If you try the 'dp' optimizer on this contraction (a tree graph taken from #112):

'ab,ab,bc,bc,ce,ce,ei,ei,ej,ej,cf,cf,fk,fk,fl,fl,bd,bd,dg,dg,gm,gm,gn,gn,dh,dh,ho,ho,hp,hp->'

it's veeery slow for shapes=[(2, 2)] * 30 but very fast in the asymptotic case where the dimensions get bigger, e.g. for shapes=[(100, 100)] * 30. However, it finds the same path in both cases.

Is this just some quirk on the cost_cap strategy or can we take advantage of this more generally to make 'dp' faster? Are there contractions where scaling up all the dimensions by the same factor leads to different sub-optimal paths for the original contraction?

cc @mrader1248

mrader1248 commented 4 years ago

Is it correct that this is not yet solved? Does any of the visual representations in the mentioned issue correspond to the contraction above?

yaroslavvb commented 4 years ago

It's the complete binary tree of depth 5 image

Behavior is still present in master, this colab is an easy way to reproduce https://colab.research.google.com/drive/14JwffnpbyxlQUv93js7JzZ2j38VIE2FD

Search time jumps 150x when going from factor size 10,10 to factor size 9,9

dgasmith commented 4 years ago

@mrader1248 Do you have a bit of time to look into this?

yaroslavvb commented 4 years ago

A work-around is to use size option when creating optimizer, the slowdown is not observed in such case. IE opt=DynamicProgramming(minimize='size')

I'm curious why this algorithm gives such a jump in computation time for a tree but not for a chain, they should have the same complexity.