Nodes in ContractionTree with same indices sets

[refraction-ray]

Hi, there. Very great project to play with!
I have a question on the construction of ContractionTree object.
In building such a tree structure, it seems to me that the node is totally determined by the frozen set of its edge indices.
I am wondering whether tensors with the same indices can be well handled in the setups, or at least they should be automatically contracted first?
Say trace of matrix square

t = ctg.core.ContractionTree.from_path([{0,1}, {1,0}], [], {0:2, 1:2}, ssa_path=[(0,1)])

I am afraid such a contractiontree may have problem since it cannot actually differentiate nodes.

t.children
# {frozenset({frozenset({0, 1})}): (frozenset({frozenset({0, 1})}), frozenset({frozenset({0, 1})}))}
t.total_flops()
# 0

Note how children and parent nodes are somehow messed with the same label and how total flops is zero which is not true for the trace operation.

I guess such scenario is a corner case, and such nodes should be contracted before contructing the tree? Though it would be great such automatic contraction and correct flop counting are also taken care of by tree construction in the program.

[jcmgray]

Hey thanks. Yes this type of thing is sadly not supported currently - and this issue has come up a few times in opt_einsum as well in fact (e.g. here and here and here). I see three possible options:

1. Simply check and raise an issue that repeated edge sets are not compatible
2. Automatically perform the hadamard deduplications first, i.e. construct that bit of the tree automatically
3. Change the internal representation, maybe such that each node is a frozenset of ints, with an extra map of these integers to the indices (could just be a list but might add some extra mental burden/complexity)

To be honest not sure if 2 would be possible without doing 3!

Do you think this a potentially common case in your uses?

[refraction-ray]

I have read the above issues and they are indeed very informative. I believe it is very important to have these preprocessing as you mentioned: hadamard de-duplication and single index reduction. I guess the case here is a special case of hadmard deduplication? ij,ji,ab...->ab... compared to more general ij,ji,ijab...->....
As shown by dgasmith/opt_einsum#112, such preprocess is useful for optimizing many types of expressions. So really hope opt_einsum will have them soon!

[jcmgray]

Ah I don't want to give the impression these are not supported in opt_einsum - they are - the issues were that some of the path finders weren't finding good paths in certain edge cases, suggesting it might be sensible to deal with them separately at the start.

The difference here is that cotengras contraction tree object actually can't represent them at all.

[refraction-ray]

Well, I guess if such preprocess happens before calling any optimizer in opt_einsum, then HyperOptimizer here is okay since what it accepts is tensors without repetitive indices (already processed by opt_einsum). And by such architecture, no path finders need to implement their own preprocessing stuff. Is this a good way to go?

[kastoryano]

Hi, I am repeatedly getting the following uninformative error when trying to run the hyperoptimizer. For instance, from the readme file:

import opt_einsum as oe
import cotengra as ctg

eq, shapes = oe.helpers.rand_equation(30, 4)
opt = ctg.HyperOptimizer()
path, info = oe.contract_path(eq, *shapes, shapes=True, optimize=opt)

---

BrokenProcessPool Traceback (most recent call last)
in
4 eq, shapes = oe.helpers.rand_equation(30, 4)
5 opt = ctg.HyperOptimizer()
----> 6 path, info = oe.contract_path(eq, *shapes, shapes=True, optimize=opt)

/Library/Frameworks/Python.framework/Versions/3.8/lib/python3.8/site-packages/opt_einsum/contract.py in contract_path(*operands, **kwargs)
257 elif isinstance(path_type, paths.PathOptimizer):
258 # Custom path optimizer supplied
--> 259 path = path_type(input_sets, output_set, dimension_dict, memory_arg)
260 else:
261 path_optimizer = paths.get_path_fn(path_type)

/Library/Frameworks/Python.framework/Versions/3.8/lib/python3.8/site-packages/cotengra-0.1.0-py3.8.egg/cotengra/hyper.py in call(self, inputs, output, size_dict, memory_limit)
345
346 # assess the trials
--> 347 for trial in trials:
348
349 # keep track of all costs and sizes

/Library/Frameworks/Python.framework/Versions/3.8/lib/python3.8/site-packages/cotengra-0.1.0-py3.8.egg/cotengra/hyper.py in _gen_results_parallel(self, repeats, trial_fn, trial_args)
310
311 if len(self._futures) >= self.pre_dispatch:
--> 312 yield self.get_and_report_next_future()
313
314 while self._futures:

/Library/Frameworks/Python.framework/Versions/3.8/lib/python3.8/site-packages/cotengra-0.1.0-py3.8.egg/cotengra/hyper.py in get_and_report_next_future(self)
294 if future.done():
295 del self._futures[i]
--> 296 trial = future.result()
297 self.report_result(method, params, trial)
298 return trial

/Library/Frameworks/Python.framework/Versions/3.8/lib/python3.8/concurrent/futures/_base.py in result(self, timeout)
430 raise CancelledError()
431 elif self._state == FINISHED:
--> 432 return self.__get_result()
433
434 self._condition.wait(timeout)

/Library/Frameworks/Python.framework/Versions/3.8/lib/python3.8/concurrent/futures/_base.py in __get_result(self)
386 def __get_result(self):
387 if self._exception:
--> 388 raise self._exception
389 else:
390 return self._result

BrokenProcessPool: A process in the process pool was terminated abruptly while the future was running or pending.

Any ideas what is hapening?

[jcmgray]

Hi @kastoryano, looks like you are maybe new to github - try creating a new, separate issue for your problem (unless you suspect its related to this one!), as a first step, I'd use ctg.HyperOptimizer(parallel=False) to give you cleaner error.

[jcmgray]

@refraction-ray I actually changed the internal representation of the nodes in recent commits so just should work now, feel free to reopen if not!