Timeline for Is there a fast way to do this tensor power/trace operation?
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 14, 2023 at 1:32 | comment | added | Craig | Correction: degree 4 in the $\lambda$s. | |
| Nov 14, 2023 at 0:43 | comment | added | Craig | I was wondering if the specific form here had a simpler solution by means of something like a set of eigenvectors/eigenmatrices. For example, assuming $M>N>P$ and looking for $N*P$ matrices V such that $\sum_{mn'p'} T_{mnp} T_{mn'p'} V_{n'p'} = \lambda V_{np}$; finding a set of non-zero such $\lambda$ and then expressing this trace as some symmetric polynomial of degree 8 in the $\lambda$s. This would take memory on the order of $O(MNP)$ and time maybe $O(MN^3P^3)$ -- which is not optimal timewise but better in terms of space. | |
| Nov 13, 2023 at 15:58 | comment | added | Igor Khavkine | @SidharthGhoshal Sorry, my remark should be corrected to refer only to the one explicit example from your question. The most general formulation, as far as I know, is a very hard problem and quite possibly open. | |
| Nov 13, 2023 at 15:32 | comment | added | Sidharth Ghoshal | Actually if $(i,j)$ is viewed as a single index then that product AGAIN reduces to the operation described : mathoverflow.net/questions/376540/… but I don't know if this can be simplified further. This suggests to me a notion of "prime contraction" or "indivisible" contraction might be a well founded concept | |
| Nov 13, 2023 at 15:28 | comment | added | Sidharth Ghoshal | @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 | |
| Nov 13, 2023 at 13:46 | comment | added | Igor Khavkine | @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. | |
| Nov 13, 2023 at 13:41 | comment | added | Igor Khavkine | @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. | |
| Nov 13, 2023 at 3:51 | comment | added | Sidharth Ghoshal | Ah here is old question of mine. Unfortunately it didn’t seem to get any answers either: cstheory.stackexchange.com/questions/52019/… | |
| Nov 13, 2023 at 3:49 | comment | added | Sidharth Ghoshal | 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. | |
| Nov 13, 2023 at 3:31 | history | asked | Craig | CC BY-SA 4.0 |