Opened 9 years ago
Closed 9 years ago
#13461 closed enhancement (fixed)
Another WeylCharacterRing speedup
Reported by: | bump | Owned by: | bump |
---|---|---|---|
Priority: | major | Milestone: | sage-5.5 |
Component: | combinatorics | Keywords: | Weyl character ring, Demazure characters, Demazure-Lusztig operators |
Cc: | sage-combinat | Merged in: | sage-5.5.beta0 |
Authors: | Daniel Bump | Reviewers: | Anne Schilling |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
After trac_13461-demazure-speedup.patch, if a WeylCharacterRing? is created with style="coroots",
characters are computed using not the Freudenthal multiplicity formula, but
rather the Demazure character formula. This can be done using only integer
addition and subtraction. If we run sage -t --long weyl_characters.py
,
it is more than twice as fast (26 seconds versus 69 seconds) as previously.
If we omit --long
it is slightly slower, so there is a speedup for
big computations and a slight penalty for small ones.
Demazure characters are added as a method of WeylCharacterRing? and the Demazure operators and Demazure-Lusztig operators are implemented as methods of WeightRing? elements.
For documentation see:
Apply:
trac_13461-demazure-speedup.patch
Attachments (1)
Change History (33)
comment:1 Changed 9 years ago by
- Description modified (diff)
- Status changed from new to needs_review
- Work issues needs testing and tweaking deleted
comment:2 Changed 9 years ago by
comment:3 Changed 9 years ago by
- Description modified (diff)
comment:4 follow-up: ↓ 5 Changed 9 years ago by
- Description modified (diff)
comment:5 in reply to: ↑ 4 Changed 9 years ago by
I can confirm that this patch gives a major speedup for the long tests in /combinat/root_systems/weyl_characters.py:
28.6 seconds versus 69.9 seconds
Without the long option I get 13.4 seconds versus 12.1 seconds.
Here are a couple of comments on the patch:
- Nicolas taught me that the standard doc strings should have a one-line description, followed by the INPUT and then, if necessary, a longer description. It might be good to follow these standards.
- Do you want to keep the "debug" options in _demazure_helper? If so, please give a short description of what it is for and a doc test with it.
- In demazure_character you refer to analogous methods in WeightRing? elements and as methods of crystals. It might be good to link these using :meth:, so this is an easy click in the documentation.
- Would it make sense to briefly explain how the notation in
sage: A2=WeylCharacterRing("A2",style="coroots") sage: sage: h=sum(A2.fundamental_weights()) sage: A2.demazure_character(h,word=[1,2]) a2(0,0) + a2(-2,1) + a2(2,-1) + a2(1,1) + a2(-1,2)
and
sage: C = CrystalOfTableaux(['A',2],shape=[2,1]) sage: C.demazure_character([1,2],reduced_word=True) x1^2*x2 + x1^2*x3 + x1*x2^2 + x1*x2*x3 + x2^2*x3
match?
- The description of the patch trac_13461-demazure-lusztig.patch seems to refer to itself "Depends on trac_13461-demazure-lusztig.patch". Perhaps it is best to fold both patches.
- There is a spurious "xo" in line 548 in trac_13461-demazure-lusztig.patch.
- It might be good to use REFERENCES: for the references in demazure_lusztig. It currently does not read well after
sage -docbuild reference html
.
So much for now!
Anne
comment:6 Changed 9 years ago by
- Keywords Weyl character ring Demazure characters Demazure-Lusztig operators added
- Reviewers set to Anne Schilling
- Status changed from needs_review to needs_work
comment:7 follow-up: ↓ 8 Changed 9 years ago by
Regarding the link that Anne suggested to the method of ClassicalCrystals
I tried:
:meth:`sage.categories.classical_crystals.ClassicalCrystals.demazure_character`
.
This doesn't produce an html link. Note that demazure_character is a ParentMethod
of the
ClassicalCrystals
Class. I wasn't able to find any similar examples in the sage documentation.
How do I do this?
comment:8 in reply to: ↑ 7 ; follow-up: ↓ 9 Changed 9 years ago by
Replying to bump:
Regarding the link that Anne suggested to the method of
ClassicalCrystals
I tried::meth:`sage.categories.classical_crystals.ClassicalCrystals.demazure_character`
. This doesn't produce an html link. Note that demazure_character is aParentMethod
of theClassicalCrystals
Class. I wasn't able to find any similar examples in the sage documentation.How do I do this?
Hi Dan,
Most likely you need
:meth:`~sage.categories.classical_crystals.ClassicalCrystals.demazure_character`
(with the tilde in front of sage).
Anne
comment:9 in reply to: ↑ 8 Changed 9 years ago by
Replying to aschilling:
:meth:`~sage.categories.classical_crystals.ClassicalCrystals.demazure_character`
I guess:
:meth:`~sage.categories.classical_crystals.ClassicalCrystals.ParentMethods.demazure_character`
which in fact should be should be shortenable to:
:meth:`ClassicalCrystals.ParentMethods.demazure_character`
Now it could well be that the above links currently break because #9107. In that case, just use this last form and the link will eventually work.
Thanks!
comment:10 follow-ups: ↓ 11 ↓ 12 Changed 9 years ago by
Thanks ... I thought I tried that.
Do you want to keep the "debug" options in _demazure_helper? If so, please give a short description of what it is for and a doc test with it.
My experience (with GNU Go) is that it is a good idea to leave debug code in for something this complicated. There is also debug code in the Freudenthal method. However this code is not meant to be used in normal operation. A doctest would look something like this:
sage: A2=WeylCharacterRing("A2",style="coroots") sage: A2.demazure_character((1,1),word=[1,2],debug=True) cm[1]=(2, -1) cm[2]=(-1, 2) i=2 v=(1, 1), coroot=1 mu=(1, 1), next[mu]=1 mu=(2, -1), next[mu]=1 i=1 v=(2, -1), coroot=2 mu=(2, -1), next[mu]=1 mu=(0, 0), next[mu]=1 mu=(-2, 1), next[mu]=1 v=(1, 1), coroot=1 mu=(1, 1), next[mu]=1 mu=(-1, 2), next[mu]=1 a2(0,0) + a2(-2,1) + a2(2,-1) + a2(1,1) + a2(-1,2)
This can be really helpful for figuring out what the code is doing but I'm dubious that a doctest is appropriate. Should I take the code out?
comment:11 in reply to: ↑ 10 Changed 9 years ago by
This can be really helpful for figuring out what the code is doing but I'm dubious that a doctest is appropriate. Should I take the code out?
If you think the debug code it useful to have around, you can leave it in. I have just never seen this before integrated into sage.
Anne
comment:12 in reply to: ↑ 10 Changed 9 years ago by
Replying to bump:
This can be really helpful for figuring out what the code is doing but I'm dubious that a doctest is appropriate. Should I take the code out?
A quick grep shows a couple of occurences of a similar idiom in e.g. schemes/elliptic_curves/ell_finite_field.py
. So I guess it's ok as long as it is consistent with what's done there.
Cheers,
Nicolas
comment:13 Changed 9 years ago by
- Description modified (diff)
- Status changed from needs_work to needs_review
comment:14 Changed 9 years ago by
Per Anne's recommendations:
The patches are now folded, xo is gone, :meth:
is used :meth:
odically
and most methods in weyl_characters.py
now have docstrings consisting
of a single line followed by INPUT and then further doc. I added a sentence
comparing the Demazure methods of crystals.
I did not take out the debugging code per discussion in comments 10, 11 and 12.
I did not use REFERENCES but instead reformulated the citations for DL operators so they look good in the reference manual.
comment:15 follow-up: ↓ 16 Changed 9 years ago by
Apply trac_13461-demazure-speedup.patch
comment:16 in reply to: ↑ 15 Changed 9 years ago by
Hi Dan,
The patch looks good and the tests pass on my machine. Here are some trivial remarks about the documentation that you might still want to fix:
- In the demazure_lusztig method replace devisible -> divisible
- In the method symmetric_power something went wrong between h_k and p_k
(at least on the website link you posted).
Other than this, positive review!
Anne
comment:17 Changed 9 years ago by
I made the corrections in comment:16.
comment:18 Changed 9 years ago by
- Status changed from needs_review to positive_review
comment:19 Changed 9 years ago by
Apply trac_13461-demazure-speedup.patch
comment:20 Changed 9 years ago by
- Milestone changed from sage-5.4 to sage-5.5
comment:21 Changed 9 years ago by
Apply trac_13461-demazure-speedup.patch
comment:22 Changed 9 years ago by
I don't understand the patchbot's red light. The patchbot says apply failed, but there is no error message in the log, just "timed out".
comment:23 Changed 9 years ago by
Apply trac_13461-demazure-speedup.patch
comment:24 Changed 9 years ago by
- Status changed from positive_review to needs_info
Just noticed that this ticket is already at positive review. I think this means that the patchbot will not run the ticket any more. I'm temporarily setting this back to needs review to test my theory :)
comment:25 Changed 9 years ago by
- Status changed from needs_info to needs_review
comment:26 Changed 9 years ago by
- Status changed from needs_review to positive_review
Yes, that did the trick.
comment:27 Changed 9 years ago by
The tracbot found some whitespace at trailing lines and the tracbot light turned blue ... I therefore reposted the patch. I will change the status to needs_info, kick, then change it back to positive_review.
The changes only delete some whitespace at ends of lines.
comment:28 Changed 9 years ago by
- Status changed from positive_review to needs_info
comment:29 Changed 9 years ago by
There is nothing wrong with trailing whitespace, its purely advisory at this point. Feel free to remove whitespace from the changed lines, but don't introduce additional changes just as a sacrifice to the whitespace gods.
comment:30 Changed 9 years ago by
- Status changed from needs_info to needs_review
comment:31 Changed 9 years ago by
- Status changed from needs_review to positive_review
comment:32 Changed 9 years ago by
- Merged in set to sage-5.5.beta0
- Resolution set to fixed
- Status changed from positive_review to closed
Apply trac_13461-demazure-speedup.patch