:py:mod:`cotengra.pathfinders.path_basic` ========================================= .. py:module:: cotengra.pathfinders.path_basic .. autoapi-nested-parse:: Basic optimization routines. Module Contents --------------- Classes ~~~~~~~ .. autoapisummary:: cotengra.pathfinders.path_basic.ContractionProcessor cotengra.pathfinders.path_basic.EnsureInputsOutputAreSequence cotengra.pathfinders.path_basic.GreedyOptimizer cotengra.pathfinders.path_basic.RandomGreedyOptimizer cotengra.pathfinders.path_basic.OptimalOptimizer Functions ~~~~~~~~~ .. autoapisummary:: cotengra.pathfinders.path_basic.is_simplifiable cotengra.pathfinders.path_basic.compute_simplified cotengra.pathfinders.path_basic.compute_contracted cotengra.pathfinders.path_basic.compute_size cotengra.pathfinders.path_basic.compute_flops cotengra.pathfinders.path_basic.compute_con_cost_flops cotengra.pathfinders.path_basic.compute_con_cost_size cotengra.pathfinders.path_basic.compute_con_cost_write cotengra.pathfinders.path_basic.compute_con_cost_combo cotengra.pathfinders.path_basic.compute_con_cost_limit cotengra.pathfinders.path_basic.parse_minimize_for_optimal cotengra.pathfinders.path_basic.linear_to_ssa cotengra.pathfinders.path_basic.ssa_to_linear cotengra.pathfinders.path_basic.is_ssa_path cotengra.pathfinders.path_basic.optimize_simplify cotengra.pathfinders.path_basic.optimize_greedy cotengra.pathfinders.path_basic.optimize_random_greedy_track_flops cotengra.pathfinders.path_basic.optimize_optimal cotengra.pathfinders.path_basic.get_optimize_greedy cotengra.pathfinders.path_basic.get_optimize_random_greedy_track_flops cotengra.pathfinders.path_basic.get_optimize_optimal .. py:function:: is_simplifiable(legs, appearances) Check if ``legs`` contains any diag (repeated) or reduced (appears nowhere else) indices. .. py:function:: compute_simplified(legs, appearances) Compute the diag and reduced legs of a term. This function assumes that the legs are already sorted. It handles the case where a index is both diag and reduced (i.e. traced). .. py:function:: compute_contracted(ilegs, jlegs, appearances) Compute the contracted legs of two terms. .. py:function:: compute_size(legs, sizes) Compute the size of a term. .. py:function:: compute_flops(ilegs, jlegs, sizes) Compute the flops cost of contracting two terms. .. py:function:: compute_con_cost_flops(temp_legs, appearances, sizes, iscore, jscore) Compute the total flops cost of a contraction given by temporary legs, also removing any contracted indices from the temporary legs. .. py:function:: compute_con_cost_size(temp_legs, appearances, sizes, iscore, jscore) Compute the max size of a contraction given by temporary legs, also removing any contracted indices from the temporary legs. .. py:function:: compute_con_cost_write(temp_legs, appearances, sizes, iscore, jscore) Compute the total write cost of a contraction given by temporary legs, also removing any contracted indices from the temporary legs. .. py:function:: compute_con_cost_combo(temp_legs, appearances, sizes, iscore, jscore, factor) Compute the combined total flops and write cost of a contraction given by temporary legs, also removing any contracted indices from the temporary legs. The combined cost is given by: cost = flops + factor * size .. py:function:: compute_con_cost_limit(temp_legs, appearances, sizes, iscore, jscore, factor) Compute the combined total flops and write cost of a contraction given by temporary legs, also removing any contracted indices from the temporary legs. The combined cost is given by: cost = max(flops, factor * size) I.e. assuming one or another to be the limiting factor. .. py:function:: parse_minimize_for_optimal(minimize) Given a string, parse it into a function that computes the cost of a contraction. The string can be one of the following: - "flops": compute_con_cost_flops - "size": compute_con_cost_size - "write": compute_con_cost_write - "combo": compute_con_cost_combo - "combo-{factor}": compute_con_cost_combo with specified factor - "limit": compute_con_cost_limit - "limit-{factor}": compute_con_cost_limit with specified factor This function is cached for speed. .. py:class:: ContractionProcessor(inputs, output, size_dict, track_flops=False, flops_limit=float('inf')) A helper class for combining bottom up simplifications, greedy, and optimal contraction path optimization. .. py:attribute:: __slots__ :value: ('nodes', 'edges', 'indmap', 'appearances', 'sizes', 'ssa', 'ssa_path', 'track_flops', 'flops',... .. py:method:: copy() .. py:method:: neighbors(i) Get all neighbors of node ``i``. .. py:method:: print_current_terms() .. py:method:: remove_ix(ix) Drop the index ``ix``, simply removing it from all nodes and the edgemap. .. py:method:: pop_node(i) Remove node ``i`` from the graph, updating the edgemap and returning the legs of the node. .. py:method:: add_node(legs) Add a new node to the graph, updating the edgemap and returning the node index of the new node. .. py:method:: check() Check that the current graph is valid, useful for debugging. .. py:method:: contract_nodes(i, j, new_legs=None) Contract the nodes ``i`` and ``j``, adding a new node to the graph and returning its index. .. py:method:: simplify_batch() Find any indices that appear in all terms and remove them, since they simply add an constant factor to the cost of the contraction, but create a fully connected graph if left. .. py:method:: simplify_single_terms() Take any diags, reductions and traces of single terms. .. py:method:: simplify_scalars() Remove all scalars, contracting them into the smallest remaining node, if there is one. .. py:method:: simplify_hadamard() .. py:method:: simplify() .. py:method:: subgraphs() .. py:method:: optimize_greedy(costmod=1.0, temperature=0.0, seed=None) .. py:method:: optimize_optimal_connected(where, minimize='flops', cost_cap=2, search_outer=False) .. py:method:: optimize_optimal(minimize='flops', cost_cap=2, search_outer=False) .. py:method:: optimize_remaining_by_size() This function simply contracts remaining terms in order of size, and is meant to handle the disconnected terms left after greedy or optimal optimization. .. py:function:: linear_to_ssa(path, N=None) Convert a path with recycled linear ids to a path with static single assignment ids. For example:: >>> linear_to_ssa([(0, 3), (1, 2), (0, 1)]) [(0, 3), (2, 4), (1, 5)] .. py:function:: ssa_to_linear(ssa_path, N=None) Convert a path with static single assignment ids to a path with recycled linear ids. For example:: >>> ssa_to_linear([(0, 3), (2, 4), (1, 5)]) [(0, 3), (1, 2), (0, 1)] .. py:function:: is_ssa_path(path, nterms) Check if an explicitly given path is in 'static single assignment' form. .. py:function:: optimize_simplify(inputs, output, size_dict, use_ssa=False) Find the (likely only partial) contraction path corresponding to simplifications only. Those simplifiactions are: - ignore any indices that appear in all terms - combine any repeated indices within a single term - reduce any non-output indices that only appear on a single term - combine any scalar terms - combine any tensors with matching indices (hadamard products) :param inputs: The indices of each input tensor. :type inputs: tuple[tuple[str]] :param output: The indices of the output tensor. :type output: tuple[str] :param size_dict: A dictionary mapping indices to their dimension. :type size_dict: dict[str, int] :param use_ssa: Whether to return the contraction path in 'SSA' format (i.e. as if each intermediate is appended to the list of inputs, without removals). :type use_ssa: bool, optional :returns: **path** -- The contraction path, given as a sequence of pairs of node indices. :rtype: list[list[int]] .. py:function:: optimize_greedy(inputs, output, size_dict, costmod=1.0, temperature=0.0, simplify=True, use_ssa=False) Find a contraction path using a greedy algorithm. :param inputs: The indices of each input tensor. :type inputs: tuple[tuple[str]] :param output: The indices of the output tensor. :type output: tuple[str] :param size_dict: A dictionary mapping indices to their dimension. :type size_dict: dict[str, int] :param costmod: When assessing local greedy scores how much to weight the size of the tensors removed compared to the size of the tensor added:: score = size_ab / costmod - (size_a + size_b) * costmod This can be a useful hyper-parameter to tune. :type costmod: float, optional :param temperature: When asessing local greedy scores, how much to randomly perturb the score. This is implemented as:: score -> sign(score) * log(|score|) - temperature * gumbel() which implements boltzmann sampling. :type temperature: float, optional :param simplify: Whether to perform simplifications before optimizing. These are: - ignore any indices that appear in all terms - combine any repeated indices within a single term - reduce any non-output indices that only appear on a single term - combine any scalar terms - combine any tensors with matching indices (hadamard products) Such simpifications may be required in the general case for the proper functioning of the core optimization, but may be skipped if the input indices are already in a simplified form. :type simplify: bool, optional :param use_ssa: Whether to return the contraction path in 'single static assignment' (SSA) format (i.e. as if each intermediate is appended to the list of inputs, without removals). This can be quicker and easier to work with than the 'linear recycled' format that `numpy` and `opt_einsum` use. :type use_ssa: bool, optional :returns: **path** -- The contraction path, given as a sequence of pairs of node indices. :rtype: list[list[int]] .. py:function:: optimize_random_greedy_track_flops(inputs, output, size_dict, ntrials=1, costmod=(0.1, 4.0), temperature=(0.001, 1.0), seed=None, simplify=True, use_ssa=False) Perform a batch of random greedy optimizations, simulteneously tracking the best contraction path in terms of flops, so as to avoid constructing a separate contraction tree. :param inputs: The indices of each input tensor. :type inputs: tuple[tuple[str]] :param output: The indices of the output tensor. :type output: tuple[str] :param size_dict: A dictionary mapping indices to their dimension. :type size_dict: dict[str, int] :param ntrials: The number of random greedy trials to perform. The default is 1. :type ntrials: int, optional :param costmod: When assessing local greedy scores how much to weight the size of the tensors removed compared to the size of the tensor added:: score = size_ab / costmod - (size_a + size_b) * costmod It is sampled uniformly from the given range. :type costmod: (float, float), optional :param temperature: When asessing local greedy scores, how much to randomly perturb the score. This is implemented as:: score -> sign(score) * log(|score|) - temperature * gumbel() which implements boltzmann sampling. It is sampled log-uniformly from the given range. :type temperature: (float, float), optional :param seed: The seed for the random number generator. :type seed: int, optional :param simplify: Whether to perform simplifications before optimizing. These are: - ignore any indices that appear in all terms - combine any repeated indices within a single term - reduce any non-output indices that only appear on a single term - combine any scalar terms - combine any tensors with matching indices (hadamard products) Such simpifications may be required in the general case for the proper functioning of the core optimization, but may be skipped if the input indices are already in a simplified form. :type simplify: bool, optional :param use_ssa: Whether to return the contraction path in 'single static assignment' (SSA) format (i.e. as if each intermediate is appended to the list of inputs, without removals). This can be quicker and easier to work with than the 'linear recycled' format that `numpy` and `opt_einsum` use. :type use_ssa: bool, optional :returns: * **path** (*list[list[int]]*) -- The best contraction path, given as a sequence of pairs of node indices. * **flops** (*float*) -- The flops (/ contraction cost / number of multiplications), of the best contraction path, given log10. .. py:function:: optimize_optimal(inputs, output, size_dict, minimize='flops', cost_cap=2, search_outer=False, simplify=True, use_ssa=False) Find the optimal contraction path using a dynamic programming algorithm (by default excluding outer products). The algorithm is an optimized version of Phys. Rev. E 90, 033315 (2014) (preprint: https://arxiv.org/abs/1304.6112), adapted from the ``opt_einsum`` implementation. :param inputs: The indices of each input tensor. :type inputs: tuple[tuple[str]] :param output: The indices of the output tensor. :type output: tuple[str] :param size_dict: A dictionary mapping indices to their dimension. :type size_dict: dict[str, int] :param minimize: How to compute the cost of a contraction. The default is "flops". Can be one of: - "flops": minimize with respect to total operation count only (also known as contraction cost) - "size": minimize with respect to maximum intermediate size only (also known as contraction width) - "write": minimize with respect to total write cost only - "combo" or "combo-{factor}": minimize with respect sum of flops and write weighted by specified factor. If the factor is not given a default value is used. - "limit" or "limit-{factor}": minimize with respect to max (at each contraction) of flops or write weighted by specified factor. If the factor is not given a default value is used. 'combo' is generally a good default in term of practical hardware performance, where both memory bandwidth and compute are limited. :type minimize: str, optional :param cost_cap: The maximum cost of a contraction to initially consider. This acts like a sieve and is doubled at each iteration until the optimal path can be found, but supplying an accurate guess can speed up the algorithm. :type cost_cap: float, optional :param search_outer: Whether to allow outer products in the contraction path. The default is False. Especially when considering write costs, the fastest path is very unlikely to include outer products. :type search_outer: bool, optional :param simplify: Whether to perform simplifications before optimizing. These are: - ignore any indices that appear in all terms - combine any repeated indices within a single term - reduce any non-output indices that only appear on a single term - combine any scalar terms - combine any tensors with matching indices (hadamard products) Such simpifications may be required in the general case for the proper functioning of the core optimization, but may be skipped if the input indices are already in a simplified form. :type simplify: bool, optional :param use_ssa: Whether to return the contraction path in 'single static assignment' (SSA) format (i.e. as if each intermediate is appended to the list of inputs, without removals). This can be quicker and easier to work with than the 'linear recycled' format that `numpy` and `opt_einsum` use. :type use_ssa: bool, optional :returns: **path** -- The contraction path, given as a sequence of pairs of node indices. :rtype: list[list[int]] .. py:class:: EnsureInputsOutputAreSequence(f) .. py:method:: __call__(inputs, output, *args, **kwargs) .. py:function:: get_optimize_greedy(accel='auto') .. py:function:: get_optimize_random_greedy_track_flops(accel='auto') .. py:class:: GreedyOptimizer(costmod=1.0, temperature=0.0, simplify=True, accel='auto') Bases: :py:obj:`cotengra.oe.PathOptimizer` Class interface to the greedy optimizer which can be instantiated with default options. .. py:attribute:: __slots__ :value: ('costmod', 'temperature', 'simplify', '_optimize_fn') .. py:method:: maybe_update_defaults(**kwargs) .. py:method:: ssa_path(inputs, output, size_dict, **kwargs) .. py:method:: search(inputs, output, size_dict, **kwargs) .. py:method:: __call__(inputs, output, size_dict, **kwargs) .. py:class:: RandomGreedyOptimizer(max_repeats=32, costmod=(0.1, 4.0), temperature=(0.001, 1.0), seed=None, simplify=True, accel='auto', parallel='auto') Bases: :py:obj:`cotengra.oe.PathOptimizer` Lightweight random greedy optimizer, that eschews hyper parameter tuning and contraction tree construction. This is a stateful optimizer that should not be re-used on different contractions. :param max_repeats: The number of random greedy trials to perform. :type max_repeats: int, optional :param costmod: When assessing local greedy scores how much to weight the size of the tensors removed compared to the size of the tensor added:: score = size_ab / costmod - (size_a + size_b) * costmod It is sampled uniformly from the given range. :type costmod: (float, float), optional :param temperature: When asessing local greedy scores, how much to randomly perturb the score. This is implemented as:: score -> sign(score) * log(|score|) - temperature * gumbel() which implements boltzmann sampling. It is sampled log-uniformly from the given range. :type temperature: (float, float), optional :param seed: The seed for the random number generator. Note that deterministic behavior is only guaranteed within the python or rust backend (the `accel` parameter) and parallel settings. :type seed: int, optional :param simplify: Whether to perform simplifications before optimizing. These are: - ignore any indices that appear in all terms - combine any repeated indices within a single term - reduce any non-output indices that only appear on a single term - combine any scalar terms - combine any tensors with matching indices (hadamard products) Such simpifications may be required in the general case for the proper functioning of the core optimization, but may be skipped if the input indices are already in a simplified form. :type simplify: bool, optional :param accel: Whether to use the accelerated `cotengrust` backend. If "auto" the backend is used if available. :type accel: bool or str, optional :param parallel: Whether to use parallel processing. If "auto" the default is to use threads if the accelerated backend is not used, and processes if it is. :type parallel: bool or str, optional .. attribute:: best_ssa_path The best contraction path found so far. :type: list[list[int]] .. attribute:: best_flops The flops (/ contraction cost / number of multiplications) of the best contraction path found so far. :type: float .. py:method:: maybe_update_defaults(**kwargs) .. py:method:: ssa_path(inputs, output, size_dict, **kwargs) .. py:method:: search(inputs, output, size_dict, **kwargs) .. py:method:: __call__(inputs, output, size_dict, **kwargs) .. py:function:: get_optimize_optimal(accel='auto') .. py:class:: OptimalOptimizer(minimize='flops', cost_cap=2, search_outer=False, simplify=True, accel='auto') Bases: :py:obj:`cotengra.oe.PathOptimizer` Class interface to the optimal optimizer which can be instantiated with default options. .. py:attribute:: __slots__ :value: ('minimize', 'cost_cap', 'search_outer', 'simplify', '_optimize_fn') .. py:method:: maybe_update_defaults(**kwargs) .. py:method:: ssa_path(inputs, output, size_dict, **kwargs) .. py:method:: search(inputs, output, size_dict, **kwargs) .. py:method:: __call__(inputs, output, size_dict, **kwargs)