cotengrust provides fast rust implementations of contraction ordering primitives for tensor networks or einsum expressions. The two main functions are:

• optimize_optimal(inputs, output, size_dict, **kwargs)
• optimize_greedy(inputs, output, size_dict, **kwargs)

The optimal algorithm is an optimized version of the opt_einsum 'dp' path - itself an implementation of https://arxiv.org/abs/1304.6112.

There is also a variant of the greedy algorithm, which runs ntrials of greedy, randomized paths and computes and reports the flops cost (log10) simultaneously:

• optimize_random_greedy_track_flops(inputs, output, size_dict, **kwargs)

Installation

cotengrust is available for most platforms from PyPI:

pip install cotengrust

or if you want to develop locally (which requires pyo3 and maturin):

git clone https://github.com/jcmgray/cotengrust.git
cd cotengrust
maturin develop --release

(the release flag is very important for assessing performance!).

Usage

If cotengrust is installed, then by default cotengra will use it for its greedy, random-greedy, and optimal subroutines, notably subtree reconfiguration. You can also call the routines directly:

import cotengra as ctg
import cotengrust as ctgr
# specify an 8x8 square lattice contraction
inputs, output, shapes, size_dict = ctg.utils.lattice_equation([8, 8])
# find the optimal 'combo' contraction path
%%time
path = ctgr.optimize_optimal(inputs, output, size_dict, minimize='combo')
# CPU times: user 13.7 s, sys: 83.4 ms, total: 13.7 s
# Wall time: 13.7 s
# construct a contraction tree for further introspection
tree = ctg.ContractionTree.from_path(
    inputs, output, size_dict, path=path
)
tree.plot_rubberband()

Benchmarks

The following benchmarks illustrate performance and may be a useful comparison point for other implementations.

First, the runtime of the optimal algorithm on random 3-regular graphs, with all bond sizes set to 2, for different mimimize targets:

Taken over 20 instances, lines show mean and bands show standard error on mean. Note how much easier it is to find optimal paths for the maximum intermediate size or cost only (vs. total for all contractions). While the runtime generally scales exponentially, for some specific geometries it might reduce to polynomial.

For very large graphs, the random_greedy optimizer is appropriate, and there is a tradeoff between how long one lets it run (ntrials) and the best cost it achieves. Here we plot these for various