Solutions to Problem Sets
Problem Set 1 Solutions:
Pb.1(a):

find the optimal contraction sequence for this network (assume all indices are of equal dimension d).
â€‹

what is the leading order computational cost of this contraction? Express your answer as a power of d.
Pb.1(b):
Ans: Contraction Sequence
Index ordering conventions:
Network contraction:
Pb.1(b)
Initialize rank3 random tensors A, B, C (assuming all indices are dimension d = 20). Write code to evaluate the network contraction (using the specified index orders) in three different ways:
â€‹

As a single summation â€‹â€‹over all internal indices using FOR loops.

As a sequence of binary contractions implemented using 'permute' and 'reshape'.

Using the 'ncon' routine.
â€‹
Check that all three approaches produce the same output tensor D, and compare their respective computation times.
Ans: MATLAB code
Problem Set 2 Solutions:
Elementwise definition:
Pb.2: Tensor A is an order4 tensor that we define elementwise as given above. Note that the difference between the MATLAB/Julia and Python definitions follows from the use of 1based indexing in the former versus the use 0based indexing in the latter, but it is still the same tensor between all three programming languages.
â€‹
(a) Assume that indices i, j are of dimension d1 and indices k, l are of dimension d2 (with d2 < d1). How does the cost of taking the SVD across the indicated partition scale with d1 and d2?
â€‹
(b) Generate the tensor A for d1 = 10 and d2 = 8. What is the norm â€–Aâ€–? After computing the norm construct the normalized tensor: A' = A / â€–Aâ€–.
â€‹
(c) Take the SVD of A' across the indicated partition. Check that the square root of the sum of the singular values squared is equal to 1. Why is this the case?
â€‹
(d) What is the effective rank r(Î”) of A' at Î” = 1e4 ?
â€‹
(e) Compute the truncation error Îµ of the restricted rank approximation r(Î”=1e4) indirectly using the singular values as per Fig.2.4(c)
â€‹
(f) Construct the optimal restricted rank approximation to A' via the truncated SVD. Compute the truncation error Îµ of this approximation and check that your answer is consistent with part (e).
Ans:
(a) Cost is O(d1^2 âˆ™ d2^4), given as the larger matrix dimension times the square of the smaller matrix dimension.
(b) Norm: â€–Aâ€– â‰ˆ 554.256
â€‹
(c) Square root of the sum of the singular values squared is equal to the tensor norm, and we have normalized such that â€–A'â€– = 1.
â€‹
(d) Effective rank r(Î” = 1e4) = 3.
â€‹
(e) Truncation error Îµ0 = 1.048e5.
â€‹
(f) Truncation error Îµ1 = 1.048e5, consistent with the previous answer.
Ans: MATLAB code
Problem Set 3 Solutions:
Fig.P3(a):
Fig.P3(b):
Pb.3: Consider the tensor network {A,B,C} â†’ H of Fig.P3(a), with the elementwise definition of tensor A is given in Fig.P3(b) (note that the definition has been modified to account for 1based indexing of MATLAB/Julia versus 0based indexing of python). Define tensors B and C equivalently such that A = B = C, and assume that all tensor indices are of dimension d=12.
â€‹
(a) Contract the network {A,B,C} to form the H tensor explicitly. Evaluate the norm â€–Hâ€–.
Fig.P3(c):
Fig.P3(d):
(b) Use the truncated SVD to optimally decompose C into a rank Ï‡=2 product of tensors, C â†’ CL â‹… CR, as depicted in Fig.P3(c). Contract the new network {A,B,CL,CR} to form a single tensor H1, as depicted in Fig.P3(d). Compute the truncation error Îµ = â€–H  H1â€– / â€–Hâ€–.
Fig.P3(e):
(c) Starting from the original network {A,B,C}, transform tensor C into a center of orthogonality using the â€˜pullingâ€™ through approach based on the QR decomposition, obtaining a new network of tensors {Aâ€™,Bâ€™,Câ€™}. Evaluate this network to a single tensor H' as depicted in Fig.P3(e), and then check that â€–H  H'â€– = 0.
Fig.P3(f):
(d) Repeat the truncation step from part (b) on the transformed tensor C' â†’ CL' â‹… CR', as depicted in Fig.P3(f), again keeping rank Ï‡=2. Contract the new network {A',B',CL',CR'} to form a single tensor H1'. Compute the truncation error Îµ' = â€–H  H1'â€– / â€–Hâ€–, and confirm that it is smaller than the result from (b). Why is this the case?
Ans:
(a) â€–Hâ€– = 1.73e7
â€‹
(b) Truncation error Îµ = â€–H  H1â€– / â€–Hâ€– = 9.45e7
â€‹
(d) Truncation error Îµ' = â€–H  H1'â€– / â€–Hâ€– = 1.06e7. The truncation error from (d) is smaller since tensor C' was transformed into a center of orthogonality before truncation, which guarantees that the global truncation error is minimized.
Ans: MATLAB code
Problem Set 4 Solutions:
Fig.P4(a):
Pb.4: Consider the tensor H with the elementwise definition given in Fig.P4(a) (note that the definition has been modified to account for 1based indexing of MATLAB/Julia versus 0based indexing of python).
â€‹
(a) Generate tensor H assuming all indices are dimension d = 6 and evaluate the norm â€–Hâ€–. Define the normalized tensor H1 = H / â€–Hâ€–
Fig.P4(b):
(b) Use a multistage decomposition to split H1 into a network of three tensors {A,B,C} while truncating to index dimension Ï‡=6 as depicted in Fig.P4(b). Compute the truncation error Îµ = â€–H1  H2â€–, where H2 is the tensor recovered from contracting {A,B,C}.
Fig.P4(c):
(c) Make the appropriate change of gauge such that the AB link becomes a center of orthogonality with a diagonal link matrix Ïƒ' as depicted in Fig.P4(d). What are the singular values in Ïƒ'? Check the validity if your gauge transformation by confirming that the singular values Ïƒ' in match those obtained directly from the SVD of tensor H2 across the equivalent partition.
Fig.P4(di):
(dii):
(d) Assume that the network T in Fig.P4(di) is in canonical form. Depicted in (dii) is the partial tensor trace of T with its conjugate network. Draw the simplified network that results from using properties of the canonical form to cancel tensors whereever possible.
Ans:
(a) â€–Hâ€– = 6.389e2
â€‹
(b) Truncation error Îµ = â€–H1  H2â€– = 1.338e7
â€‹
(c) Singular values: {0.999958, 9.107e3, 7.975e5, 1.613e6}
â€‹
(d) Canonical form implies the branch to the left of the AD link annihilates to the identity with its conjugate, therefore the network simplifies as depicted below: