Abstract
The contraction cost of a tensor network depends on the contraction order. However, the optimal contraction ordering problem is known to be NP-hard. We show that the linear contraction ordering problem for tree tensor networks admits a polynomial-time algorithm, by drawing connections to database join ordering. The result relies on the adjacent sequence interchange property of the contraction cost, which enables a global decision of the contraction order based on local comparisons. Based on that, we specify a modified version of the IKKBZ database join ordering algorithm to find the optimal tree tensor network linear contraction order. Finally, we extend our algorithm as a heuristic to general contraction orders and arbitrary tensor network topologies.
Original language | English |
---|---|
Pages (from-to) | B647-B668 |
Journal | SIAM Journal on Scientific Computing |
Volume | 46 |
Issue number | 5 |
DOIs | |
State | Published - 2024 |
Keywords
- contraction ordering
- database join ordering
- dynamic programming
- einsum
- optimal algorithm
- tensor networks