Note

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

Speedup of the C++ extension

The package torchtt has an optional C++ extension that implements two algorithms:

Both algorithms are also implemented in Python. The Python implementation is used when the extension is not available or when use_cpp=False is passed. The C++ code calls the same kind of PyTorch functions (tensor contractions, QR and singular value decompositions, linear solves) as the Python code, without the Python overhead between these calls. The C++ AMEn solver also needs fewer of these calls: its local GMRES solver orthogonalizes a new vector against all previous ones with two matrix-vector products instead of one dot product per previous vector, and its rank truncation checks several ranks at once. This notebook compares the runtimes of the two implementations for a few problem sizes.

Imports:

[1]:
import time
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

Is the C++ extension available?

The extension is compiled when the package is installed on Linux or macOS. If it is not available, use_cpp=True falls back to Python and both implementations below have the same runtime.

[2]:
print('C++ extension available:', tntt.cpp_enabled())
C++ extension available: True

Timing

The function timing() calls f() once to warm up and returns the average runtime of n_runs further calls together with the result of the last call.

[3]:
def timing(f, n_runs=5):
    f()
    tme = time.perf_counter()
    for _ in range(n_runs):
        result = f()
    tme = (time.perf_counter() - tme) / n_runs
    return tme, result

AMEn solver

We solve \(-\Delta u = 1\) in \([0,1]^d\) with \(u = 0\) on the boundary using finite differences with \(n\) interior points in every direction. The finite difference matrix is a sum of Kronecker products of the one-dimensional matrix with identity matrices and is constructed directly in the TT format:

[4]:
def laplacian(d, n):
    """
    Finite difference matrix of the negative Laplacian in d dimensions with n interior points in every direction.
    """
    h = 1 / (n + 1)
    L1d = (2 * tn.eye(n, dtype=tn.float64) - tn.diag(tn.ones(n - 1, dtype=tn.float64), 1) - tn.diag(tn.ones(n - 1, dtype=tn.float64), -1)) / h**2
    L1d = tntt.TT(L1d, [(n, n)])
    L = L1d ** tntt.eye([n] * (d - 1)) + tntt.eye([n] * (d - 1)) ** L1d
    for i in range(1, d - 1):
        L = L + tntt.eye([n] * i) ** L1d ** tntt.eye([n] * (d - 1 - i))
    return L.round(1e-14)

The right-hand side is a tensor of ones. The system is solved with both implementations and the same arguments for a few values of \(d\) and \(n\). The relative residuals show that both implementations reach the same accuracy.

[5]:
print('  d    n   C++ [s]   Python [s]   speedup   residual C++   residual Python')
for d, n in [(4, 8), (16, 8), (8, 32), (4, 128)]:
    A = laplacian(d, n)
    b = tntt.ones([n] * d)
    t_cpp, x_cpp = timing(lambda: tntt.solvers.amen_solve(A, b, eps=1e-8, use_cpp=True))
    t_py, x_py = timing(lambda: tntt.solvers.amen_solve(A, b, eps=1e-8, use_cpp=False))
    res_cpp = ((A @ x_cpp - b).norm() / b.norm()).item()
    res_py = ((A @ x_py - b).norm() / b.norm()).item()
    print('%3d %4d %9.3f %12.3f %9.1f %14.1e %17.1e' % (d, n, t_cpp, t_py, t_py / t_cpp, res_cpp, res_py))
  d    n   C++ [s]   Python [s]   speedup   residual C++   residual Python
  4    8     0.011        0.074       6.7        1.1e-10           8.2e-11
 16    8     0.054        0.284       5.3        7.0e-10           6.1e-10
  8   32     0.111        0.621       5.6        3.2e-09           3.2e-09
  4  128     0.641        1.862       2.9        3.8e-09           3.6e-09

DMRG matrix-vector product

A random TT matrix of rank 3 is multiplied with random TT tensors of increasing rank using the DMRG method. Both implementations run the same algorithm, so the comparison holds whether or not DMRG is the fastest method for this product (the example on AMEn and DMRG for fast TT operations compares the methods). The errors are relative to the exact product A @ x.

[6]:
d, n = 16, 4
A = tntt.random([(n, n)] * d, [1] + [3] * (d - 1) + [1])
print('rank of x   C++ [s]   Python [s]   speedup   error C++   error Python')
for r in [2, 8, 32]:
    x = tntt.random([n] * d, [1] + [r] * (d - 1) + [1])
    y_ref = A @ x
    t_cpp, y_cpp = timing(lambda: tntt.matvec(A, x, eps=1e-10, method=tntt.methods.DMRG(use_cpp=True)))
    t_py, y_py = timing(lambda: tntt.matvec(A, x, eps=1e-10, method=tntt.methods.DMRG(use_cpp=False)))
    err_cpp = ((y_cpp - y_ref).norm() / y_ref.norm()).item()
    err_py = ((y_py - y_ref).norm() / y_ref.norm()).item()
    print('%9d %9.3f %12.3f %9.1f %11.1e %14.1e' % (r, t_cpp, t_py, t_py / t_cpp, err_cpp, err_py))
rank of x   C++ [s]   Python [s]   speedup   error C++   error Python
        2     0.009        0.018       2.0     8.2e-15        5.6e-15
        8     0.031        0.044       1.4     1.1e-14        9.8e-15
       32     0.276        0.294       1.1     1.3e-14        1.4e-14

Conclusion

The speedup is largest when the TT cores are small (small mode sizes and ranks): every PyTorch call is then cheap and the Python overhead between the calls dominates the runtime. For the largest cores (\(n = 128\)) more of the time is spent inside PyTorch and the speedup is smaller. The DMRG matrix-vector product gains less than the AMEn solver: singular value decompositions dominate its runtime, and the C++ AMEn solver also needs fewer PyTorch calls. The timings depend on the hardware and on the number of threads used by PyTorch. To check the speedup for your own problem, compare the runtimes with use_cpp=True and use_cpp=False, an argument of torchtt.solvers.amen_solve() and of torchtt.methods.DMRG().