[Numpy-discussion] Performance of einsum?

[Jaakko Luttinen]

Hi,

I was wondering if someone could provide some intuition on the
performance of einsum?

I have found that sometimes it is extremely efficient but sometimes it
is several orders of magnitudes slower compared to some other
approaches, for instance, using multiple dot-calls.

My intuition is that the computation time of einsum is linear with
respect to the size of the "index space", that is, the product of the
maximums of the indices.

So, for instance computing the dot product of three matrices A*B*C would
not be efficient as einsum('ij,jk,kl->il', A, B, C) because there are
four indices i=1,...,I, j=1,...,J, k=1,...,K and l=1,...,L so the total
computation time is O(I*J*K*L) which is much worse than with two dot
products O(I*J*K+J*K*L), or with two einsum-calls for Y=A*B and Y*C.

On the other hand, computing einsum('ij,ij,ij->i', A, B, C) would be
"efficient" because the computation time is only O(I*J).

Is this intuition roughly correct or how could I intuitively understand
when the usage of einsum is bad?

Best regards,
Jaakko