einsum_path greedy optimize ignores memory limit in some cases

[adamjermyn]

The documentation for numpy.einsum_path says that if a tuple is provided for the optimize keyword argument the second element in the tuple is interpreted as a memory limit on intermediate matrices. This seems to not be quite true: the source (einsumfunc.py) between lines 738 and 741 ignores the specified memory limit if the greedy algorithm is selected and if the memory limit exceeds the size of the largest input or output. On line 739 there is a comment explaining this as a requirement for the greedy algorithm, but this doesn't seem to be true and the comment is not consistent with the following line (the comment specifies that the maximum memory should be at most out_size, but the following line compares it against max_size).

At a minimum this should be documented in the parameter description and the comment should refer to the correct variable. More importantly though it seems that there are cases where this behaviour is undesirable. For instance, the contraction

'ikl,plm,mki->p'

will not produce intermediate arrays when run with greedy optimization because every single-index contraction creates an intermediate larger than any of the inputs or the output. There may be cases where creating an intermediate which is slightly larger is acceptable if it saves a large number of operations. In this particular case the 'optimal' option can be used and avoids this, but longer constructions exist for which the optimal option is not practical. For instance

'abc,def,ghi,gda,jki,lmn,cfo,lpq,mrs,opt,jru,vwq,sxk,bwt,euh,nvx->'

can be contracted with intermediates with no more than five indices (this comes from a matrix product state). The optimal path finder is extremely slow at determining an order with this many indices while the greedy one attempts to sum over 24 indices simultaneously because it won't create any intermediates larger than the inputs or outputs.

[charris]

There is ongoing work on einsum at https://github.com/dgasmith/opt_einsum. Might take a look.

[adamjermyn]

Ah indeed this seems to be fixed in that version. Thanks!

[charris]

I'll leave this open until numpy is updated.

[mattip]

@charris how does the update happen? Do the opt_einsum devs submit pull requests to NumPy?

[charris]

Someone does. Note that a fair amount of divergence may be taking place. @dgasmith Do you plan to keep maintaining the NumPy code.

[dgasmith]

@charris Absolutely, it's mostly a question of how much testing is required when we do these deep changes. einsum is used in more ways than I can count and these changes do effect the overall behavior- we think they are isolated, but it isn't always the case.

I think this particular issue is clear cut, I can make a PR.

[charris]

@dgasmith Great. Might also want to track the NEP at #11189, einsum was one of the functions it was intended for. See also https://matthewrocklin.com/blog//work/2018/05/27/beyond-numpy.