Compressed contraction path finding using branch and bound.

Module Contents#



Exhaustively search all possible contraction orders for a given



do_reconfigure(tree, time, chi)

class cotengra.experimental.path_compressed_branchbound.CompressedExhaustive(minimize, max_nodes=float('inf'), max_time=None, local_score=None, exploration_power=0.0, best_score=None, progbar=False)#

Exhaustively search all possible contraction orders for a given compressed bond dimension, using several forms of pruning and local hueristics to accelerate the search.

  • chi (int) – The max bond dimension of the compressed hypergraph.

  • max_nodes (int, optional) – Set the maximum number of contraction steps to consider.

  • max_time (float, optional) – Set the maximum time to spend on the search.

  • local_score (callable, optional) –

    A function that assigns a score to a potential contraction, with a lower score giving more priority to explore that contraction earlier. It should have signature:

    local_score(step : int, tracker: CompressedStatsTracker) -> float

    where step is the number of steps so far, tracker is a CompressedStatsTracker object that tracks various properties like flops and peak size.

  • exploration_power (float, optional) – If not 0.0, the inverse power to which the step is raised in the default local score function. Higher values favor exploring more promising branches early on - at the cost of increased memory. Ignored if local_score is supplied.

  • best_score (float, optional) – Manually specify an upper bound for best score found so far.

  • progbar (bool, optional) – If True, display a progress bar.

property ssa_path#
property path#
setup(inputs, output, size_dict)#

Set-up the optimizer with a specific contraction.

expand_node(i, j, hg, tree_map, ssa_path, tracker, high_priority=False)#

Given a current contraction node, expand it by contracting nodes i and j.

  • i (int) – The nodes to contract.

  • j (int) – The nodes to contract.

  • hg (Hypergraph) – The hypergraph to contract.

  • ssa_path (list) – The contraction path so far.

  • tracker (CompressedStatsTracker) – Scoring object that tracks costs of current compressed contraction.

  • high_priority (bool, optional) – If True, the contraction will be assessed before any other normal contractions.


The contraction index, or None if the contraction is guaranteed to be worse than another contraction.

Return type:

int or None

_update_progbar(pbar, c)#
run(inputs, output, size_dict)#
explore_path(path, high_priority=True, restrict=False)#

Explicitly supply a path to be added to the search space, by default it is added to the priority queue and will be processed first.

  • path (sequence[tuple[int]]) – A contraction path to explore.

  • high_priority (bool, optional) – If True, the path will be assessed before anything else, regardless of cost - the default.

  • restrict (bool, optional) – If True, only allow contractions in this path, so only the order will be optimized.

search(inputs, output, size_dict)#

Run and return the best ContractionTreeCompressed.

__call__(inputs, output, size_dict)#

Run and return the best path.

cotengra.experimental.path_compressed_branchbound.do_reconfigure(tree, time, chi)#
class cotengra.experimental.path_compressed_branchbound.CompressedTreeRefiner(trees, copt, chi, max_refine_time=8, executor=None, pre_dispatch=8, progbar=False, plot=False)#
_check_score(key, tree, score=None)#
_process_result(tree, key, time, old, new)#
refine(num_its=None, bins=30)#