Creating tensors

A new tensor is added to the network by a drag-and-drop gesture. The user drags a special “create tensor” symbol (blue circle in Figure 2) to the desired location. When “dropping” the symbol, a new tensor (black circle) appears there. Initially it has zero legs. The tensors are automatically labeled 0, 1, 2, … to provide a unique identifier. The “create tensor” symbol reappears at its default location after this operation, and can then be used to add another tensor to the network.

Attaching tensor legs

Each leg represents one dimension of the tensor. The user creates a new leg by “pulling” it out of the tensor (i.e., drag-and-drop on the tensor), when simultaneously holding the Control key. Each tensor and its legs can still be freely moved around within the GUI window.

Tensor contractions

Tensor contractions are specified by connecting the tips of tensor legs. The tips snap to each other when brought into close contact. The actual contraction (possibly of several tensors) is executed when pressing the “Contract” button of the GUI, see Figure 3 for an example.

Splitting a tensor

The splitting of a tensor by QR or singular value decomposition (SVD) is a ubiquitous operation in tensor network algorithms, in particular for reducing “bond dimensions” by devising a singular value cut-off tolerance, and a prerequisite for working with left- and right-orthogonal tensors in the MPS framework [3]. The first step for decomposing a tensor A is its “matricization”: a subset of legs is grouped together into one “fat” leg and the remaining (complementary) legs into a second “fat” leg. The two fat legs are interpreted as the rows and columns of a matrix, which is then decomposed. Figure 4 illustrates this process (as it appears in the GUI) for the QR decomposition of a tensor with initially 5 legs. (An analogous SVD decomposition is currently still under development.) The user first right-clicks on a tensor to initiate the splitting operation. An overlay window then asks for the ordering and partitioning of dimensions attributed to the rows and columns in the matricization process. In the example, the “row” consists of dimensions 0, 3, 2 (in this order) and the “column” of dimensions 1, 4 (in this order). After the decomposition, the resulting Q and R matrices are finally reshaped to restore the original dimensions, with an additional dimension for the shared bond (last dimension of Q, first dimension of R). Thus the dimensions 0, 1, 2 of Q match the original dimensions 0, 3, 2, and dimensions 1, 2 of R the original dimensions 1, 4.

The initial reordering of dimensions becomes a separate “elementary transposition operation”, as described below. The generated code uses a temporary tensor for this purpose. In Figure 4, this temporary tensor has index 1, and hence the Q and R tensors are consecutively labeled 2 and 3.

After this reordering, the partitioning is simply a reinterpretation of the data stored in the tensor, since the “row” group now consists of the first ℓ leading dimensions, and the “column” group of the remaining r – ℓ trailing dimensions, where the rank r is the total number of dimensions.

(i) Elementary contraction of tensors

The GuiTeNet framework supports general contraction operations on a tensor network. An elementary contraction acts on a subset of tensors such that these tensors are joined (directly or indirectly) by shared legs, yielding a single tensor after the contraction. Note that “multi-bond” contractions, i.e., the simultaneous contraction of multiple legs as in Figure 3, is explicitly allowed. In principle, a contraction of several tensors could be decomposed into a sequence of pairwise contractions, e.g., computing the matrix product ABC by first “contracting” A with B to obtain T = AB and then multiplying T with C. However, in general the optimal order of these pairwise contractions poses a delicate optimization problem [7] and is not straightforwardly applicable to multi-bond contractions. Hence we regard the contraction of (possibly more than two) tensors as elementary operation, and leave the optimized implementation to backend software packages.

On the other hand, a sequence of tensor network operations can be optimized by merging subsequent elementary contractions into a single elementary contraction. As simple (toy model) illustration why this might be useful, consider the contraction C = AB (matrix-matrix multiplication) followed by the contraction y = Cx(matrix-vector product). Merging these two contractions leads to y = ABx, for which a backend algorithm would naturally choose the order y = A(Bx).

To uniquely specify a contraction operation, we follow NumPy’s einsum command convention in the form einsum (T₀, s₀, T₁, s₁, …, s_out). Here the T_i refer to tensors, and s_i are lists of integer labels for the corresponding dimensions, with multiply occurring labels to be summed over. The last argument s_out determines the ordering of dimensions in the output tensor after the contraction. For the example in Figure 3 with 4 tensors,

s₀ = (0, 1, 2), s₁ = (0, 1, 3), s₂ = (0, 4), s₃ = (4, 5) and s_out = (2, 3, 5).

Thus, the three dimensions of tensor T₀ are labeled 0, 1, 2, the three dimensions of tensor T₁ are labeled 0, 1, 3 etc. The dimensions labeled 0, 1 and 4 will be contracted since they appear multiple times, and the remaining dimensions are ordered as (2, 3, 5) in the output tensor. The generated Python source code follows exactly this scheme and reads explicitly

T4 = np.einsum(T0, (0, 1, 2), T1, (0, 1, 3),
               T2, (0, 4), T3, (4, 5), (2, 3, 5))

(ii) General transposition of a tensor

Formally, a tensor transposition is a permutation of dimensions, generalizing the usual transposition of matrices. For example, applying the permutation (1, 2, 0) to a 10 × 11 × 12 tensor T yields a 11 × 12 × 10 tensor, such that the (i, j, k)-th entry of T is the (j, k, i)-th entry of the transposed tensor. Since the tensor elements are typically stored as a contiguous array in memory, a transposition implies a reshuffling of the array elements. Thus, while a transposition does not involve arithmetic calculations besides computing memory addresses, its cost can still be significant, in particular due to the inherent “cache-unfriendliness”.

Specifying a transposition only requires designating the permutation of dimensions. We follow the convention of NumPy’s transpose function.

Regarding transpositions as separate elementary operations — instead of first step for splitting a tensor for example — facilitates additional optimizations. A plausible scenario is integrating the transposition into a preceding contraction operation [13], generalizing (AB^T)^T = BA^T for matrices A and B.

(iii) QR decomposition of a tensor

The elementary QR decomposition considered here does not involve any reordering of dimensions. Thus, it is uniquely specified by the number ℓ of leading tensor dimensions to be interpreted as “row” dimension in the matricization process, and correspondingly the remaining dimensions as “column” dimension.

To illustrate, the generated Python code (up to renaming variables) for the elementary QR decomposition of a tensor T and ℓ = 3 leading dimensions reads as follows:

Q, R = np.linalg.qr(T.reshape((np.prod(T.shape[:3]),
       np.prod(T.shape[3:]))), mode=’reduced’)
Q = Q.reshape(T.shape[:3] + (Q.shape[1],))
R = R.reshape((R.shape[0],) + T.shape[3:])

The reshape functions implement the matricization before and “de-matricization” after the actual QR decomposition, T.shape stores the tensor dimensions, np.prod computes the product of the leading and trailing dimensions, and np.linalg.qr implements the conventional QR decomposition of matrices.

(iv) Singular-value decomposition of a tensor

The (de-)matricization process for an elementary singular-value decomposition (SVD) of a tensor is analogous to the elementary QR decomposition. The output now consists of three tensors, corresponding to the U, S and V matrices of the matrix-SVD, with the diagonal S matrix storing the singular values. Additional parameters (compared to the QR decomposition) are a cut-off tolerance for the singular values, and optionally the maximally allowed number of singular values (the maximal “bond” dimension).

Strategies for optimization

Based on the elementary tensor network operations, several high-level optimization strategies are conceivable, solely based on the rank of each tensor instead of the actual dimensions. The implementation of the following ideas is left for future work.

• A natural representation for the sequence of user actions is a directed acyclic graph (DAG), storing an elementary operation or input tensor at each node. Such a representation clarifies dependencies, and allows to determine which operations can be executed in parallel.
• A more subtle optimization strategy tailored to tensor networks is the merging of subsequent contractions, i.e., if the tensor resulting from a contraction is immediately used in another contraction. A toy model example consists of merging C = AB followed by y = Cx into y = ABx, which can then be evaluated in the order y = A(Bx). Note that the optimized computational cost for the merged contraction cannot be higher than performing the contractions sequentially (since the latter restricts the allowed contraction order), but actually determining the optimal order for the merged contraction (by a backend software package) is in general more difficult [7].
• Another optimization strategy is avoiding explicit transpositions (i.e., permutations of tensor dimensions), and aiming for advantageous dimension ordering. As mentioned, the transposition of a tensor resulting from a contraction can be integrated into the contraction (see also [13]), generalizing (AB^T)^T = BA^T for matrices. Transpositions may also be pushed through the computational graph; for example, instead of permuting the leading dimensions of the Q-tensor resulting from a QR decomposition, one could already permute these dimensions in the input tensor, or vice versa. Conversely, in case a transposition has to be performed, optimized software packages are available [9, 14].

Code repository GitHub

Name: guitenet

Persistent identifier: https://github.com/GuiTeNet/guitenet

Licence: MIT License

Date published: 01/08/2018