Opened 7 years ago

Closed 7 years ago

#14402 closed enhancement (fixed)

Implement tensor product of infinite crystals

Reported by: tscrim Owned by: sage-combinat
Priority: major Milestone: sage-5.11
Component: combinatorics Keywords: infinite crystals, tensor product
Cc: sage-combinat, aschilling, bsalisbury1 Merged in: sage-5.11.beta0
Authors: Ben Salisbury, Travis Scrimshaw Reviewers: Anne Schilling
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #14454, #14266 Stopgaps:

Description (last modified by tscrim)

Currently tensor product of infinite crystals does not work well, likely due to assumptions that the crystals are finite. This implements a new tensor product of crystals class for handling infinite crystals.


Apply:

Attachments (1)

trac_14402-tensor_product_infinite_crystals-ts.patch (56.9 KB) - added by tscrim 7 years ago.

Download all attachments as: .zip

Change History (11)

comment:1 Changed 7 years ago by tscrim

  • Dependencies set to #14454

comment:2 follow-up: Changed 7 years ago by bsalisbury1

  • Milestone changed from sage-5.9 to sage-5.10
  • Status changed from new to needs_review

comment:3 in reply to: ↑ 2 Changed 7 years ago by aschilling

Hi Ben and Travis,

Thanks for your work on this! Here are some initial comments:

  • The patch needs proper header (needs to be exported).
  • Please remove the period at the end of line 379 of tensor_product.py
  • It might be easier to explain the tensor product rule using the signature rule (in addition to the formulas that you use). That is more conceptual and usually easier to follow. Also, you introduce the notation a_i(k), but then you do not actually use it in the formulas for \varepsilon and \varphi. Why not?
  • You just mention "Examples with non-regular and infinite crystals::". Perhaps say a few more words what is special about them. Also, please mention the Kashiwara and antiKashiwara options in the documentation of TensorProductOfCrystals?, so that the user can find this and is aware of the options!
  • The computation of epsilon and phi in your code does not seem very efficient
            Ep = lambda k: sum(self[-j].epsilon(i) for j in range(1, k+1))
            Ph = lambda k: sum(self[-j].phi(i) for j in range(1, k))
            return max(Ep(k) - Ph(k) for k in range(1, len(self)+1))
    

You are computing the partial sums over and over. Why not something like

       a = [ self[-1].epsilon(i) ] 
       for j in range(1,k):
           a += [a[-1]+self[-j-1].epsilon(i) - self[-j].phi(i)]
       return max(a)

and similarly for phi. You could also optimize the computation of a_i(k) (which I guess is in _sig) and then use the formula of epsilon in terms of a_i(k).

  • Could you please explain why the previous implementation in CrystalOfWords? did not do the same thing?

So much for now.

Anne

comment:4 follow-up: Changed 7 years ago by tscrim

  • Dependencies changed from #14454 to #14454 #14266
  • Description modified (diff)

Hey Anne,

Here's a new version of the patch which changes the computation of epsilon and phi and caches in the parent _sig. I also added a note on the global option on convention to TensorProductOfCrystals.

I've added documentation about the signature rule, but this does not apply for non-regular crystals. For example, consider the highest weight element in B infinity tensored with itself. Both phi_i and epsilon_i are 0 for all i, so by the signature rule, this would be 0 for f_i which is not the case.

For the previous implementation, did you mean the old TensorProductOfCrystalsElement? If so, then it assumed the signature rule gave the crystal structure, which is why it didn't work. I didn't want to put this into the doc since it's an implementation detail, but if you think it should be, then we can add it in.

Also the dependency on #14266 is trivial due to a change of sources.py, and this can easily be commuted past.

Thank you for doing the review,
Travis

comment:5 in reply to: ↑ 4 Changed 7 years ago by aschilling

Hi Travis,

I left a review patch on the sage-combinat queue. In particular, I think the formula for \phi_i in terms of the a_i was not quite right in your patch, so I tried to correct it (it is now very simple, namely max(\lambda_i+a_i(k))). Please check that you agree! I also changed the code accordingly. The tests still pass. Since the change did not seem to make a difference for the tests, it might be a good idea to put some stronger tests in that check all possible cases for the \epsilon_i and \phi_i, so that you are sure that the code is doing what it is supposed to be doing (perhaps run some exhaustive tests for regular crystals in some example against the alternative implementation).

If you are happy with the review patch you can fold it in and make the above changes as well.

Thanks!

Anne

comment:6 Changed 7 years ago by tscrim

Hey Anne,

The reason why tests didn't break is because it is equivalent. To see this, note that

a_i(k+1) = a_i(k) + \epsilon_i(b_{k+1}) - \phi_i(b_k)

which is how _sig() is recursively computed. However this way is much more clear and clean. I've uploaded the folded patch and pushed to the queue.

Best,
Travis

For patchbot:

Apply: trac_14402-tensor_product_infinite_crystals-ts.patch

comment:7 Changed 7 years ago by aschilling

  • Reviewers set to Anne Schilling
  • Status changed from needs_review to positive_review

comment:8 Changed 7 years ago by jdemeyer

  • Dependencies changed from #14454 #14266 to #14454, #14266
  • Milestone changed from sage-5.10 to sage-5.11

comment:9 Changed 7 years ago by tscrim

Hey Anne,

Thank you for doing the review.

Best,
Travis

comment:10 Changed 7 years ago by jdemeyer

  • Merged in set to sage-5.11.beta0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.