search

jcmgray / cotengra

Hyper optimized contraction trees for large tensor networks and einsums
https://cotengra.readthedocs.io
Apache License 2.0
174 stars 32 forks source link

Add basic first version of random kahypar+ #35

Open CSNWEB opened 2 months ago

CSNWEB commented 2 months ago

Based on https://github.com/ti2-group/hybrid_contraction_tree_optimizer/

Unfortunately I just realized that the RandomOptimizer does not optimize the costmod and temperature. Not sure how I missed that while going over the code. Without that the results are much worse though. I think ideally these parameters should be randomly chosen within the optimize function for each trial. For now I just hacked it over the optimize functions, which will probably lose some performance in the accelerated rust case.

pep8speaks commented 2 months ago

Hello @CSNWEB! Thanks for updating this PR. We checked the lines you've touched for PEP 8 issues, and found:

There are currently no PEP 8 issues detected in this Pull Request. Cheers! :beers:

Comment last updated at 2024-05-05 00:03:57 UTC
jcmgray commented 2 months ago

Thanks for this! Yes random sampling of costmod and temperature can be very easily added to the python and rust version, though actual optimization / tuning of the distribution they sample from a bit harder. Do you have any assessment of how good the performance is with uniform sampling?

CSNWEB commented 2 months ago

The basic version I added in this PR (temperature exponential, costumed uniform), which comes from your original hyperoptimizer if I remember correctly, was very effective in my tests. It nearly always performed better in terms of best path found after x seconds than optuna or nevergrad. It definitely seems to be sufficient to find reasonably good greedy paths.

CSNWEB commented 2 months ago

I reduced the code size quite a bit by removing all the contract tree related stuff and merging the paths directly while removing the duplicated tree traversal. Apart from the hacked in costmod and temperature tuning I am happy with the code now.

jcmgray commented 2 months ago

Great, could you maybe add a basic test? e.g. just to the matrix in test_optimizers.py.

I'll take a look and add the costmod and temperature sampling soon.

jcmgray commented 2 months ago

OK I've added costmod and temperature sampling now, which yes does increase the path quality quite nicely without much drawback. It's in cotengra main now and v0.1.3 of cotengrust (https://github.com/jcmgray/cotengrust/releases/tag/v0.1.3) has it enabled also.

CSNWEB commented 1 month ago

Awesome, thanks. I will try to add some tests towards the end of the week.

CSNWEB commented 1 month ago

Just a short heads up that I haven't forgotten this, but due to some personal circumstances my time right now is quite limited, so I might not be able to have a look at this again until the end of the month or even start of July when the lecture period is over.