Note

Run this notebook in Google Colab or see the source on GitHub.

AMEn and DMRG for fast TT operations

The torchtt package includes density matrix renormalization group (DMRG; Oseledets, 2011) and alternating minimal energy (AMEn; Dolgov and Savostyanov, 2014) schemes for fast matrix vector products and elementwise inversion in the tensor-train (TT) format.

Imports:

[1]:

import torch as tn import torch as tn try: import torchtt as tntt except: print('Installing torchTT...') %pip install git+https://github.com/ion-g-ion/torchTT import torchtt as tntt import datetime

Efficient products

When performing the multiplication between a TT matrix and a TT tensor, the rank of the result is the product of the ranks of the inputs. Therefore rank rounding has to be performed. This increases the complexity to \(\mathcal{O}(dnr^6)\). If the result has a much smaller rank than the product of the ranks, the rounded result can be computed without forming the exact product, for example with the DMRG scheme proposed by Oseledets in “DMRG Approach to Fast Linear Algebra in the TT-Format”.

The functions torchtt.matvec(), torchtt.matmat() and torchtt.hadamard() compute the rounded products and the argument method chooses the algorithm:

The documentation of torchtt.methods describes which method to use when. The following function compares them.

[2]:
def compare(A, x, methods):
    """
    Compute the matrix vector product with each method and print the runtime, the rank of the result and the relative error.
    """
    y_ref = (A @ x).round(1e-12)
    for method in methods:
        tme = datetime.datetime.now()
        y = tntt.matvec(A, x, eps=1e-10, method=method)
        tme = datetime.datetime.now() - tme
        print('%-7s time %s   rank %3d   relative error %.1e' % (method, tme, max(y.R), ((y - y_ref).norm() / y_ref.norm()).item()))

Create a random TT matrix and a random TT tensor.

[3]:
n = 4 # mode size
A = tntt.random([(n,n)]*8,[1]+7*[4]+[1]) # random TT matrix
x = tntt.random([n]*8,[1]+7*[5]+[1]) # random TT tensor

Increase the ranks without adding information. The product of the ranks is now 24 * 40 = 960, but the result can be compressed to rank 20 (the product is equivalent to \(8\mathbf{\mathsf{Ax}}\)). The methods that do not form the exact product (DMRG and AMEn) are faster than 'direct' in this case.

[4]:
A_large = A + A + A + A - A - A
x_large = x + x + x + x + x + x - x - x
print('Ranks of A:', A_large.R)
print('Ranks of x:', x_large.R)
compare(A_large, x_large, ['direct', 'dmrg', 'amen', 'swap'])
Ranks of A: [1, 24, 24, 24, 24, 24, 24, 24, 1]
Ranks of x: [1, 40, 40, 40, 40, 40, 40, 40, 1]
direct  time 0:00:00.245850   rank  20   relative error 1.4e-15
dmrg    time 0:00:00.024251   rank  24   relative error 8.5e-15
amen    time 0:00:02.257294   rank  20   relative error 5.9e-15
swap    time 0:00:00.055199   rank  20   relative error 1.2e-14

If the result cannot be compressed, forming the exact product is the fastest. For random tensors, the product of the ranks is also the rank of the result (here 4 * 5 = 20).

[5]:
compare(A, x, ['direct', 'dmrg', 'amen', 'swap'])
direct  time 0:00:00.001999   rank  20   relative error 1.1e-15
dmrg    time 0:00:00.012654   rank  24   relative error 7.1e-15
amen    time 0:00:00.146048   rank  20   relative error 5.2e-15
swap    time 0:00:00.049164   rank  20   relative error 1.1e-14

The parameters of a method are changed by passing an instance of its class from torchtt.methods instead of its name. The iterative methods also accept an initial guess of the result.

[6]:
y = tntt.matvec(A_large, x_large, eps=1e-10, method=tntt.methods.DMRG(nswp=10, kickrank=2))
y = tntt.matvec(A_large, x_large, eps=1e-10, method=tntt.methods.AMEn(kickrank=8), initial=y)

The same holds for the elementwise product and the product of TT matrices.

[7]:
z = tntt.hadamard(x_large, x_large, eps=1e-10, method='dmrg')
B = tntt.matmat(A_large, A_large, eps=1e-10, method='direct')

Elementwise division in the TT format

One other basic linear algebra function that cannot be done without optimization is the elementwise division of two tensors in the TT format. In contrast to the elemntwise multiplication (where the resulting TT cores can be explicitly computed), the elementwise inversion has to be solved by means of an optimization problem (the method of choice is AMEn).

The operator “/” can be used for elemntwise division between tensors. Moreover one can use “/” between a scalar and a torchtt.TT instance.

Create 2 tensors:

  • \(\mathsf{x}_{i_1i_2i_3i_4} = 2 + i_1\)

  • \(\mathsf{y}_{i_1i_2i_3i_4} = i_1^2+i_2+i_3+1\)

and express them in the TT format. For both of them a TT decomposition of the elemmentwise inverse cannot be explicitly formed.

[8]:
N = [32,50,44,64]
I = tntt.meshgrid([tn.arange(n,dtype = tn.float64) for n in N])
x = 2+I[0]
x = x.round(1e-15)
y = I[0]*I[0]+I[1]+I[2]+I[3]+1
y = y.round(1e-15)

Perform \(\mathsf{z}_{\mathbf{i}} = \frac{\mathsf{x}_{\mathbf{i}}}{\mathsf{z}_{\mathbf{i}}}\) and report the relative error.

[9]:
z = x/y
print('Relative error', tn.linalg.norm(z.full()-x.full()/y.full())/tn.linalg.norm(z.full()))
Relative error tensor(3.3809e-11, dtype=torch.float64)

Perform \(\mathsf{u}_{\mathbf{i}} = \frac{1}{\mathsf{z}_{\mathbf{i}}}\) and report the relative error.

[10]:
u = 1/y
print('Relative error', tn.linalg.norm(u.full()-1/y.full())/tn.linalg.norm(u.full()))
Relative error tensor(1.1774e-11, dtype=torch.float64)

Following are also possible:

  • scalar (float, int) divided elementwise by a tensor in the TT format.

  • torch.tensor with 1 element divided elementwise by a tensor in the TT format.

[11]:
w = 1.0/y
a = tn.tensor(1.0)/y