Alternative contraction path algorithms

google / TensorNetwork

A library for easy and efficient manipulation of tensor networks.

Apache License 2.0

1.82k stars 359 forks source link

Alternative contraction path algorithms #120

Closed dgasmith closed 5 years ago

dgasmith commented 5 years ago

The opt_einsum repository has been working on paths for tensor contractions for a few years now and have come up with a variety of algorithms tuned for several use cases. A few algorithms to check out:

Deterministic algorithms can be found here
Some exploration of non-determistic algorithms here
Greedy algorithms with custom heuristics here
Shared intermediate algorithms here

We originally powered the optimization algorithms in the NumPy einsum function, but have expanded to a number of other projects such as Pyro. Hopefully you may find these algorithms useful as well!

chaserileyroberts commented 5 years ago

Thanks! We definitely are looking for some advancements on contraction algorithms. If you want to make a PR, we would love to include it! :)

dgasmith commented 5 years ago

Sure, we can look into it. It might be easiest to add a single algorithm at first to your contractors to see how the implementation goes. What about starting with the "optimal" algorithm?

chaserileyroberts commented 5 years ago

That would be awesome! Feel free to email me if you need any help.

amilsted commented 5 years ago

@dgasmith Out of interest: Are there any plans to do opt_einsum's path optimization in e.g. cython in the future? I am guessing it could make a significant difference to the performance of, say, the optimal path algorithm.

dgasmith commented 5 years ago

This is something I would love to do and would help our downstream packages. Making an issue on the opt_einsum GitHub would be a good place to get started and we could figure out how we would implement this. My bet that most of the bottlenecks at this point are in the cost evaluations and set logic which could have extremely fast C implementations.

Apologies for not making progress on this issue, my time is a bit swamped at the moment. I should be able to get back to this issue in September (!).

chaserileyroberts commented 5 years ago

We've added most of the determanistic algorithms from opt_einsum as of https://github.com/google/TensorNetwork/pull/173. Any upgrades to opt_einsum now will be immediately incorporated into this library. ^-^

We had some issues getting the random contractors integrated, as they seem to not exist in the pip package. (See https://github.com/dgasmith/opt_einsum/issues/93) Once that is fixed, integrating them should be one liners.