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:

Status badges

Description (last modified by bump)

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:

http://sporadic.stanford.edu/bump/reference-5.4.beta1/sage/combinat/root_system/weyl_characters.html

Apply:

trac_13461-demazure-speedup.patch

Attachments (1)

trac_13461-demazure-speedup.patch (24.6 KB) - added by bump 9 years ago.
Weyl CharacterRing? speedup: use Demazure algorithm

Download all attachments as: .zip

Change History (33)

comment:1 Changed 9 years ago by bump

  • Description modified (diff)
  • Status changed from new to needs_review
  • Work issues needs testing and tweaking deleted

comment:2 Changed 9 years ago by bump

Apply trac_13461-demazure-speedup.patch

comment:3 Changed 9 years ago by bump

  • Description modified (diff)

comment:4 follow-up: Changed 9 years ago by bump

  • Description modified (diff)

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

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 aschilling

  • 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: Changed 9 years ago by 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 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: Changed 9 years ago by aschilling

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 a ParentMethod of the ClassicalCrystals 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 nthiery

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: Changed 9 years ago by bump

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 aschilling

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 nthiery

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 bump

  • Description modified (diff)
  • Status changed from needs_work to needs_review

comment:14 Changed 9 years ago by bump

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: Changed 9 years ago by bump

Apply trac_13461-demazure-speedup.patch

comment:16 in reply to: ↑ 15 Changed 9 years ago by aschilling

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 bump

I made the corrections in comment:16.

comment:18 Changed 9 years ago by aschilling

  • Status changed from needs_review to positive_review

comment:19 Changed 9 years ago by bump

Apply trac_13461-demazure-speedup.patch

comment:20 Changed 9 years ago by jdemeyer

  • Milestone changed from sage-5.4 to sage-5.5

comment:21 Changed 9 years ago by bump

Apply trac_13461-demazure-speedup.patch

comment:22 Changed 9 years ago by bump

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 bump

Apply trac_13461-demazure-speedup.patch

comment:24 Changed 9 years ago by vbraun

  • 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 vbraun

  • Status changed from needs_info to needs_review

comment:26 Changed 9 years ago by vbraun

  • Status changed from needs_review to positive_review

Yes, that did the trick.

Changed 9 years ago by bump

Weyl CharacterRing? speedup: use Demazure algorithm

comment:27 Changed 9 years ago by bump

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.

Last edited 9 years ago by bump (previous) (diff)

comment:28 Changed 9 years ago by bump

  • Status changed from positive_review to needs_info

comment:29 Changed 9 years ago by vbraun

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 bump

  • Status changed from needs_info to needs_review

comment:31 Changed 9 years ago by bump

  • Status changed from needs_review to positive_review

comment:32 Changed 9 years ago by jdemeyer

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