{ "cells": [ { "cell_type": "markdown", "id": "e8f7e6a5", "metadata": {}, "source": [ "# Speedup of the C++ extension\n", "\n", "The package `torchtt` has an optional C++ extension that implements two algorithms:\n", "\n", "- the AMEn solver for linear systems `torchtt.solvers.amen_solve()` ([Dolgov and Savostyanov, 2014](https://doi.org/10.1137/140953289)),\n", "- the DMRG matrix-vector product `torchtt.matvec()` with `method=torchtt.methods.DMRG()` ([Oseledets, 2011](https://doi.org/10.2478/cmam-2011-0021)).\n", "\n", "Both algorithms are also implemented in Python.\n", "The Python implementation is used when the extension is not available or when `use_cpp=False` is passed.\n", "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.\n", "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.\n", "This notebook compares the runtimes of the two implementations for a few problem sizes.\n", "\n", "Imports:" ] }, { "cell_type": "code", "execution_count": 1, "id": "75a57094", "metadata": { "execution": { "iopub.execute_input": "2026-10-01T07:39:50.301514Z", "iopub.status.busy": "2026-10-01T07:39:50.301434Z", "iopub.status.idle": "2026-10-01T07:39:51.218539Z", "shell.execute_reply": "2026-10-01T07:39:51.218054Z" } }, "outputs": [], "source": [ "import time\n", "import torch as tn\n", "try:\n", " import torchtt as tntt\n", "except:\n", " print('Installing torchTT...')\n", " %pip install git+https://github.com/ion-g-ion/torchTT\n", " import torchtt as tntt" ] }, { "cell_type": "markdown", "id": "81aa9170", "metadata": {}, "source": [ "## Is the C++ extension available?\n", "\n", "The extension is compiled when the package is installed on Linux or macOS.\n", "If it is not available, `use_cpp=True` falls back to Python and both implementations below have the same runtime." ] }, { "cell_type": "code", "execution_count": 2, "id": "b57642cc", "metadata": { "execution": { "iopub.execute_input": "2026-10-01T07:39:51.220015Z", "iopub.status.busy": "2026-10-01T07:39:51.219877Z", "iopub.status.idle": "2026-10-01T07:39:51.221825Z", "shell.execute_reply": "2026-10-01T07:39:51.221480Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "C++ extension available: True\n" ] } ], "source": [ "print('C++ extension available:', tntt.cpp_enabled())" ] }, { "cell_type": "markdown", "id": "a9a65076", "metadata": {}, "source": [ "## Timing\n", "\n", "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." ] }, { "cell_type": "code", "execution_count": 3, "id": "bcd51a61", "metadata": { "execution": { "iopub.execute_input": "2026-10-01T07:39:51.222867Z", "iopub.status.busy": "2026-10-01T07:39:51.222778Z", "iopub.status.idle": "2026-10-01T07:39:51.224702Z", "shell.execute_reply": "2026-10-01T07:39:51.224322Z" } }, "outputs": [], "source": [ "def timing(f, n_runs=5):\n", " f()\n", " tme = time.perf_counter()\n", " for _ in range(n_runs):\n", " result = f()\n", " tme = (time.perf_counter() - tme) / n_runs\n", " return tme, result" ] }, { "cell_type": "markdown", "id": "eb920ff7", "metadata": {}, "source": [ "## AMEn solver\n", "\n", "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.\n", "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:" ] }, { "cell_type": "code", "execution_count": 4, "id": "edb569f6", "metadata": { "execution": { "iopub.execute_input": "2026-10-01T07:39:51.225694Z", "iopub.status.busy": "2026-10-01T07:39:51.225596Z", "iopub.status.idle": "2026-10-01T07:39:51.228764Z", "shell.execute_reply": "2026-10-01T07:39:51.228393Z" } }, "outputs": [], "source": [ "def laplacian(d, n):\n", " \"\"\"\n", " Finite difference matrix of the negative Laplacian in d dimensions with n interior points in every direction.\n", " \"\"\"\n", " h = 1 / (n + 1)\n", " 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\n", " L1d = tntt.TT(L1d, [(n, n)])\n", " L = L1d ** tntt.eye([n] * (d - 1)) + tntt.eye([n] * (d - 1)) ** L1d\n", " for i in range(1, d - 1):\n", " L = L + tntt.eye([n] * i) ** L1d ** tntt.eye([n] * (d - 1 - i))\n", " return L.round(1e-14)" ] }, { "cell_type": "markdown", "id": "f27ac4b3", "metadata": {}, "source": [ "The right-hand side is a tensor of ones.\n", "The system is solved with both implementations and the same arguments for a few values of $d$ and $n$.\n", "The relative residuals show that both implementations reach the same accuracy." ] }, { "cell_type": "code", "execution_count": 5, "id": "e38d3f14", "metadata": { "execution": { "iopub.execute_input": "2026-10-01T07:39:51.229731Z", "iopub.status.busy": "2026-10-01T07:39:51.229629Z", "iopub.status.idle": "2026-10-01T07:40:15.279043Z", "shell.execute_reply": "2026-10-01T07:40:15.278556Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " d n C++ [s] Python [s] speedup residual C++ residual Python\n", " 4 8 0.011 0.074 6.7 1.1e-10 8.2e-11\n", " 16 8 0.054 0.284 5.3 7.0e-10 6.1e-10\n", " 8 32 0.111 0.621 5.6 3.2e-09 3.2e-09\n", " 4 128 0.641 1.862 2.9 3.8e-09 3.6e-09\n" ] } ], "source": [ "print(' d n C++ [s] Python [s] speedup residual C++ residual Python')\n", "for d, n in [(4, 8), (16, 8), (8, 32), (4, 128)]:\n", " A = laplacian(d, n)\n", " b = tntt.ones([n] * d)\n", " t_cpp, x_cpp = timing(lambda: tntt.solvers.amen_solve(A, b, eps=1e-8, use_cpp=True))\n", " t_py, x_py = timing(lambda: tntt.solvers.amen_solve(A, b, eps=1e-8, use_cpp=False))\n", " res_cpp = ((A @ x_cpp - b).norm() / b.norm()).item()\n", " res_py = ((A @ x_py - b).norm() / b.norm()).item()\n", " 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))" ] }, { "cell_type": "markdown", "id": "9f5eb31c", "metadata": {}, "source": [ "## DMRG matrix-vector product\n", "\n", "A random TT matrix of rank 3 is multiplied with random TT tensors of increasing rank using the DMRG method.\n", "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).\n", "The errors are relative to the exact product `A @ x`." ] }, { "cell_type": "code", "execution_count": 6, "id": "4e54e8fe", "metadata": { "execution": { "iopub.execute_input": "2026-10-01T07:40:15.280304Z", "iopub.status.busy": "2026-10-01T07:40:15.280204Z", "iopub.status.idle": "2026-10-01T07:40:19.381856Z", "shell.execute_reply": "2026-10-01T07:40:19.381369Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "rank of x C++ [s] Python [s] speedup error C++ error Python\n", " 2 0.009 0.018 2.0 8.2e-15 5.6e-15\n", " 8 0.031 0.044 1.4 1.1e-14 9.8e-15\n", " 32 0.276 0.294 1.1 1.3e-14 1.4e-14\n" ] } ], "source": [ "d, n = 16, 4\n", "A = tntt.random([(n, n)] * d, [1] + [3] * (d - 1) + [1])\n", "print('rank of x C++ [s] Python [s] speedup error C++ error Python')\n", "for r in [2, 8, 32]:\n", " x = tntt.random([n] * d, [1] + [r] * (d - 1) + [1])\n", " y_ref = A @ x\n", " t_cpp, y_cpp = timing(lambda: tntt.matvec(A, x, eps=1e-10, method=tntt.methods.DMRG(use_cpp=True)))\n", " t_py, y_py = timing(lambda: tntt.matvec(A, x, eps=1e-10, method=tntt.methods.DMRG(use_cpp=False)))\n", " err_cpp = ((y_cpp - y_ref).norm() / y_ref.norm()).item()\n", " err_py = ((y_py - y_ref).norm() / y_ref.norm()).item()\n", " 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))" ] }, { "cell_type": "markdown", "id": "12dc5fdb", "metadata": {}, "source": [ "## Conclusion\n", "\n", "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.\n", "For the largest cores ($n = 128$) more of the time is spent inside PyTorch and the speedup is smaller.\n", "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.\n", "The timings depend on the hardware and on the number of threads used by PyTorch.\n", "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()`." ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.12.3" } }, "nbformat": 4, "nbformat_minor": 5 }