4
$\begingroup$

Well, I asked this question on Math SE, and didn't get any responses, so I'm trying it here.

Given an $M*N*P$ tensor $T$, is there a fast way of computing the following "eighth-power trace"? $$ f(T) = \sum_{m,n,p} T_{m_{00},n_{00},p_{00}} T_{m_{01},n_{01},p_{00}} T_{m_{10},n_{00},p_{01}} T_{m_{11},n_{01},p_{01}} T_{m_{00},n_{10},p_{10}} T_{m_{01},n_{11},p_{10}} T_{m_{10},n_{10},p_{11}} T_{m_{11},n_{11},p_{11}} $$ That is, imagine 8 copies of the tensor lying at the vertices of a cube and contract along all the edges. The 2-dimensional analog for an $M*N$ matrix $T$ would be $Tr( (T^t T)^2 )$. Is there any faster or less memory-intensive way than just contracting along $M$ to get a $N^2*P^2$ matrix $T' \approx T^2$ and then computing $Tr((T'^t T')^2)$?

Improve this question
$\endgroup$
9
  • 2
    $\begingroup$ Depending on reception here you might benefit posting in tcs stackexchange and cs stackexchange. I would like to believe the general problem summing over indices between products of multi-indexed variables (ie tensor contractions) should have non trivial speedups for the same reason that matrix multiplication has non trivial speed ups. $\endgroup$
    – Sidharth Ghoshal
    Commented Nov 13, 2023 at 3:49
  • $\begingroup$ Ah here is old question of mine. Unfortunately it didn’t seem to get any answers either: cstheory.stackexchange.com/questions/52019/… $\endgroup$
    – Sidharth Ghoshal
    Commented Nov 13, 2023 at 3:51
  • 1
    $\begingroup$ @SidharthGhoshal from the looks of it, the comment to your old question by Emil Jeřábek already says the most that could be said about it. $\endgroup$
    – Igor Khavkine
    Commented Nov 13, 2023 at 13:41
  • 1
    $\begingroup$ @Craig Check out the discussion under this related older question from M.SE. I don't claim any special expertise on tensor networks, but from the bag of tricks that I'm aware of, you've already found the best simplification by reducing the problem to matrix multiplication. If one of $M,N,P$ happens to be much smaller/larger than the others, then of course you could strategically choose the initial contraction to optimize the resulting matrix multiplication. $\endgroup$
    – Igor Khavkine
    Commented Nov 13, 2023 at 13:46
  • $\begingroup$ @IgorKhavkine, thanks for pointing it out! i dont know if Emil's comment addresses all contractions. His/your observation definitely is true for the 2-tensor 2-index contraction I supplied. But I question whether instead of recasting the problem as matrix muliplication there are speedups specific to the type of contraction. Something like $\sum_{i,j} a_{ijkl}b_{xijy}c_{zwij}$ at least to me doesn't seem to reduce to a single matrix multiplication in any reasonable fashion yet there might be some wild Karatsuba like trick still lurking around the corner with it $\endgroup$
    – Sidharth Ghoshal
    Commented Nov 13, 2023 at 15:28

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .