optimaltree hangs on edge case with all costs equal to 1#207
Merged
Conversation
Member
|
I only remember that the initial cost was certainly trial and error, and not particularly clever. The cost of a simple left to right contraction would probably be much more sensible. |
Member
Author
|
Test failures are unrelated, in principle this should be good to go. |
|
Thanks for the quick fix @lkdvos! Can you register a new version? |
Member
Author
|
Should be done relatively soon, but I want to include the precompilation PR as well |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Fix for #206
@Jutho correct me if I'm wrong, but I think what is going on here is that the initial guess for the
maxcostis wrong for these cases:From what I can tell we use:
Which evaluates to
1in this case, while the actual maximal cost would be(n-1) * 1withnthe number of tensors.I patched the specific case of all sizes equal to 1, but I am not sure if this now captures all possible problems. (I'm also not entirely sure where the initial formula came from?)
I could also replace this
maxcostwith the cost of simply multiplying in the order that is supplied, but I'm not sure what the implications are for the algorithm.