Efficient Decomposition of High-Rank Tensors
arXiv:1708.07471 · doi:10.1016/j.jcp.2018.10.026
Abstract
Tensors are a natural way to express correlations among many physical variables, but storing tensors in a computer naively requires memory which scales exponentially in the rank of the tensor. This is not optimal, as the required memory is actually set not by the rank but by the mutual information amongst the variables in question. Representations such as the tensor tree perform near-optimally when the tree decomposition is chosen to reflect the correlation structure in question, but making such a choice is non-trivial and good heuristics remain highly context-specific. In this work I present two new algorithms for choosing efficient tree decompositions, independent of the physical context of the tensor. The first is a brute-force algorithm which produces optimal decompositions up to truncation error but is generally impractical for high-rank tensors, as the number of possible choices grows exponentially in rank. The second is a greedy algorithm, and while it is not optimal it performs extremely well in numerical experiments while having runtime which makes it practical even for tensors of very high rank.
arXiv comment10 pages, 15 figures. Updated to match published version in J Comp Phys
References in corpus (15)
- The NumPy array: a structure for efficient numerical computation
- A Practical Introduction to Tensor Networks: Matrix Product States and Projected Entangled Pair States
- A class of quantum many-body states that can be efficiently simulated
- Simulating quantum computation by contracting tensor networks
- Tensor network states and geometry
- Second Renormalization of Tensor-Network States
- Loop optimization for tensor network renormalization
- Efficient Tree Tensor Network States (TTNS) for Quantum Chemistry: Generalizations of the Density Matrix Renormalization Group Algorithm
- Algorithms for tensor network renormalization
- Faster identification of optimal contraction sequences for tensor networks
- Renormalization group flows of Hamiltonians using tensor networks
- Singular value decomposition and matrix reorderings in quantum information theory
- Improving the efficiency of variational tensor network algorithms
- Entanglement, Tensor Networks and Black Hole Horizons
- Tensor Network Skeletonization