ON THE OPTIMAL LINEAR CONTRACTION ORDER OF TREE TENSOR NETWORKS, AND BEYOND

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
Pages (from-to)B647-B668
JournalSIAM Journal on Scientific Computing
Volume46
Issue number5
DOIs
StatePublished - 2024

Keywords

  • contraction ordering
  • database join ordering
  • dynamic programming
  • einsum
  • optimal algorithm
  • tensor networks

Fingerprint

Dive into the research topics of 'ON THE OPTIMAL LINEAR CONTRACTION ORDER OF TREE TENSOR NETWORKS, AND BEYOND'. Together they form a unique fingerprint.

Cite this