Opened 5 years ago

Closed 19 months ago

#20469 closed enhancement (fixed)

Implement Ariki-Koike algebras

Reported by: tscrim Owned by: sage-combinat
Priority: major Milestone: sage-9.1
Component: algebra Keywords: hecke algebra, complex reflection group, ariki-koike, days93.51
Cc: sage-combinat, stumpc5, andrew.mathas, tscrim Merged in:
Authors: Travis Scrimshaw, Andrew Mathas Reviewers: Andrew Mathas, Travis Scrimshaw, Sebastian Oehms
Report Upstream: N/A Work issues:
Branch: daf777e (Commits, GitHub, GitLab) Commit: daf777ec27554610ab39c5bbe31f74673238c58c
Dependencies: Stopgaps:

Status badges

Description

An Ariki-Koike algebra is the Hecke algebra of the complex reflection group G(r,1,n).

Change History (52)

comment:1 Changed 5 years ago by stumpc5

  • Cc stumpc5 added

comment:2 Changed 5 years ago by tscrim

  • Branch set to public/algebras/ariki_koike_algebras-20469
  • Cc andrew.mathas added
  • Commit set to f644c20f0c297faf9dc98e4bab70c5985131d390

Here is the first version. I still have to convert from Ariki-Koike's version to the Hu-Mathas definition, but this version seems to work (in particular, it passed a few of my associativity tests and the relations I tested). There is also more documentation that needs to be added. I'm also not completely satisfied with the default base ring. However, I wanted to get feedback.

Note that the multiplication is highly recursive. In particular, once there is an lir occurring, it can easily run into Python's recursion limit. It might be possible to work this out with handling the manipulations within the code here or doing parts of the multiplication in bigger chunks. However, this would take a lot of work I think to improve and the code works.

I am also planning on implementing the isomorphism with type An/Bn Hecke algebras shortly too.


New commits:

f644c20Initial implementation of Ariki-Koike alegbras.
Last edited 5 years ago by tscrim (previous) (diff)

comment:3 follow-up: Changed 5 years ago by andrew.mathas

Thanks Travis. This looks interesting. I will have a play with it and see if I can improve the multiplication with the tricks that I know about these algebras -- I am not promising that this will be possible, only to look!

Some initial comments:

  • It would be better to use L1,...,Ln for the Jucys-Murphy elements as this is what is commonly used in the literature and it's also consistent with using T1,T2,... for the Hecke generators. Using l1,...,ln looks strange to me.
  • I am not sure that it is worth the effort to define the Hu-Mathas as the algebras that we defined are different to these when q=1 and, more importantly, the conversion between the two is easy in principle but messy in practice.
  • The default base ring should be the smallest ring that contains q, u0,...,ur.
  • At some stage I will polish the code that I have which implements the Specht modules for these algebras. Given this it would probably be a good idea to put this code in its own subdirectory so that the module code. Similarly, my graded Specht module could go in here to.
Last edited 5 years ago by andrew.mathas (previous) (diff)

comment:4 Changed 5 years ago by git

  • Commit changed from f644c20f0c297faf9dc98e4bab70c5985131d390 to 21a49dfec02d086a07e888ecef48529dffa302b6

Branch pushed to git repo; I updated commit sha1. New commits:

79cc757Changing l -> L.
c4b3588Moving Ariki-Koike algebras to new subfolder for Hecke algebras.
fd0097fAdding more documentation and examples. Doing some fixes.
21a49dfFixing an error with multiplication of the T_i generators.

comment:5 in reply to: ↑ 3 Changed 5 years ago by tscrim

Replying to andrew.mathas:

Thanks Travis. This looks interesting. I will have a play with it and see if I can improve the multiplication with the tricks that I know about these algebras -- I am not promising that this will be possible, only to look!

Great, thanks. It is currently so recursive that it fails for L2 * L1 * L2 in H(2,2) (although L1 * (L2)^2 works).

  • It would be better to use L1,...,Ln for the Jucys-Murphy elements as this is what is commonly used in the literature and it's also consistent with using T1,T2,... for the Hecke generators. Using l1,...,ln looks strange to me.

Done.

  • I am not sure that it is worth the effort to define the Hu-Mathas as the algebras that we defined are different to these when q=1 and, more importantly, the conversion between the two is easy in principle but messy in practice.

This also leads to a question of what do we want to call the Hu-Mathas variant? In the future, we can also add another basis to this for q \neq 1. We also should probably add the basis indexed by the colored permutations (i.e., monomials in T_0, ..., T_{n-1}).

  • The default base ring should be the smallest ring that contains q, u0,...,ur.

With q invertible, that is what it currently does (just in a slightly funky way that groups the u's together then the q's).

  • At some stage I will polish the code that I have which implements the Specht modules for these algebras. Given this it would probably be a good idea to put this code in its own subdirectory so that the module code. Similarly, my graded Specht module could go in here to.

I have moved this into a hecke_algebras folder to start. We can move the rest of the Hecke algebras (e.g., Iwahori and Yokonuma) to this folder on a followup ticket.

While adding the documentation, I also found some errors with the multiplication that I have fixed.

comment:6 Changed 5 years ago by git

  • Commit changed from 21a49dfec02d086a07e888ecef48529dffa302b6 to 76e643fe3b04ff5f78d882311688e92b2aafddd6

Branch pushed to git repo; I updated commit sha1. New commits:

76e643fFixing multiplication the other way.

comment:7 Changed 5 years ago by git

  • Commit changed from 76e643fe3b04ff5f78d882311688e92b2aafddd6 to e9b6a594ae1e089b51b37081f35743402447a960

Branch pushed to git repo; I updated commit sha1. New commits:

bcd1ef4Initial implementation of Ariki-Koike alegbras.
93b57ffChanging l -> L.
a98d138Moving Ariki-Koike algebras to new subfolder for Hecke algebras.
5e739baAdding more documentation and examples. Doing some fixes.
f5f5795Fixing an error with multiplication of the T_i generators.
13fdc45Fixing multiplication the other way.
dae0031Initial review
f9cd185Merge branch 'develop' into t/20469/public/algebras/ariki_koike_algebras-20469
7282c37Rewriting product code to avoid recursion
e9b6a59Merging with remote

comment:8 follow-up: Changed 5 years ago by andrew.mathas

Hi Travis,

I have been through your code and fixed the recursion issue. It was actually an infinite recursion loop. The problem was that as the terms in the products ....T_i L_k... were being put into standard form "letter-by-letter" (so changing the previous expression to \sum ... L_m T_j...) you sometimes ended up going around in circles by pushing a T_i past an L_k that then created a large power of some L_m that, when reduced, got you back to the previous situation. I have rewritten the product_on_basis code to avoid this, so I'm afraid that I've replaced this section of your code. The product code is now less recursive with terms largely being rewritten into standard form "in place".

On top of this I proved a formula for the expansion of L_k^m that, embarrassingly, I later found in one of my papers. This was my first guess for improving the multiplication issues but once I'd made this change I discovered the recursion loop. The other main change is that I rescaled L_k to q**{1-k}*L_k, in [AK] notation, because this renormalisation is what is normally used in the literature as it works better with the combinatorics.

I have made a start at adding the documentation. As a result of the rescaling of the L_k's quite a lot of doc-tests are currently failing, being off by the corresponding power of q. I am happy to fix these. I left them in only so that you can compare if you wish. I am also happy to fill out the documentation as I know this area quite well.

Other issues that we could think about are:

  • whether to allow the two parameter version: (T_i-q1)(T_i+q2)=0. Probably quite painful as all of the product formulas will change
  • whether to implement the degenerate algebras. This might be easy as it could be done as a derived class with slightly different _product_LTwTv, _product_Tw_L, and _Li_power methods
  • I think having a slightly shorter _repr_ string would be a good idea: Ariki-Koike algebra of rank 5 with parameters q,u0,u2,u3 is enough I think
  • implementing other bases? This is probably best left for another ticket...especially as I think that the realisations code currently requires that the same indexing sets be used(?)

Any way, I think that the code now works. Please have a look and let me know what you think. Happy to be a reviewer or coauthor on the ticket as you think best.

Andrew

Last edited 5 years ago by andrew.mathas (previous) (diff)

comment:9 Changed 5 years ago by andrew.mathas

ps. With the degenerate algebras, the other option would be to use the Hu-Mathas presentation for the "main" algebra (this combines the Ariki-Koike algebras with q\ne1 and the degenerate AK algebras (when q=1) and then implement the q=1 version of the Ariki-Koike algebras as the "extra" case. I am biased, but personally I think that makes more sense because the Hu-M. presentation fits with the KLR categorifiction of integrable highest weight modules perfectly whereas the Ariki-Koike presentation does not.

comment:10 in reply to: ↑ 8 ; follow-up: Changed 5 years ago by tscrim

  • Authors changed from Travis Scrimshaw to Travis Scrimshaw, Andrew Mathas
  • Cc tscrim added
  • Milestone changed from sage-7.2 to sage-7.3
  • Reviewers set to Andrew Mathas, Travis Scrimshaw

Replying to andrew.mathas:

I have been through your code and fixed the recursion issue. It was actually an infinite recursion loop. The problem was that as the terms in the products ....T_i L_k... were being put into standard form "letter-by-letter" (so changing the previous expression to \sum ... L_m T_j...) you sometimes ended up going around in circles by pushing a T_i past an L_k that then created a large power of some L_m that, when reduced, got you back to the previous situation. I have rewritten the product_on_basis code to avoid this, so I'm afraid that I've replaced this section of your code. The product code is now less recursive with terms largely being rewritten into standard form "in place".

Thank you very much for looking through this code and fixing the problem(s). Sorry it ended up being a bit of a mess. I'm very happy you were able to improve it.

On top of this I proved a formula for the expansion of L_k^m that, embarrassingly, I later found in one of my papers. This was my first guess for improving the multiplication issues but once I'd made this change I discovered the recursion loop. The other main change is that I rescaled L_k to q**{1-k}*L_k, in [AK] notation, because this renormalisation is what is normally used in the literature as it works better with the combinatorics.

I probably could have looked harder in the literature. I'm okay with the renormalization (especially since I have more of an interest in the combinatorics too). I just kept the [AK] normalization since I was using that as my reference and didn't trust myself to correctly handle the renormalization.

I have made a start at adding the documentation. As a result of the rescaling of the L_k's quite a lot of doc-tests are currently failing, being off by the corresponding power of q. I am happy to fix these. I left them in only so that you can compare if you wish. I am also happy to fill out the documentation as I know this area quite well.

I would appreciate all of your expertise in writing the documentation. I can go over it and do any necessary formatting. I can also fix the doctests afterwards.

Other issues that we could think about are:

  • whether to allow the two parameter version: (T_i-q1)(T_i+q2)=0. Probably quite painful as all of the product formulas will change

I think it is good to try and be as general as possible when it is not much work. I agree, I think it would be very annoying to switch because we would have to redo all of the product formulas (at least, I would have to put some thought on how to do this to make everything consistent). So, I think this is plenty good for now.

  • whether to implement the degenerate algebras. This might be easy as it could be done as a derived class with slightly different _product_LTwTv, _product_Tw_L, and _Li_power methods
  • I think having a slightly shorter _repr_ string would be a good idea: Ariki-Koike algebra of rank 5 with parameters q,u0,u2,u3 is enough I think

I think we should give the base ring to better differentiate the instances. Plus this is consistent with what we do elsewhere in Sage. One slight issue is the default ring is a polynomial ring over a polynomial ring, and it is this that makes the repr very long. I decided to do this for the default ring so the q's would be grouped together.

  • implementing other bases? This is probably best left for another ticket...especially as I think that the realisations code currently requires that the same indexing sets be used(?)

I agree; this should be another ticket unless you have code ready. The realizations code itself does not require the same indexing set, but you have to do a bit more with the morphisms. For an example, see the descent algebra (combinat/descent_algebra.py).

Any way, I think that the code now works. Please have a look and let me know what you think. Happy to be a reviewer or coauthor on the ticket as you think best.

I will play around with in shortly. We will both be both coauthors and reviewers (yet again :P).

Replying to andrew.mathas:

ps. With the degenerate algebras, the other option would be to use the Hu-Mathas presentation for the "main" algebra (this combines the Ariki-Koike algebras with q\ne1 and the degenerate AK algebras (when q=1) and then implement the q=1 version of the Ariki-Koike algebras as the "extra" case. I am biased, but personally I think that makes more sense because the Hu-M. presentation fits with the KLR categorifiction of integrable highest weight modules perfectly whereas the Ariki-Koike presentation does not.

I'm +1 for getting things closer to the KLR algebra (something that I hope to eventually get into Sage at some point). Otherwise I don't have an opinion on which presentation we use. How much would have to be changed in order to move to the Hu-Mathas presentation?

comment:11 in reply to: ↑ 10 ; follow-up: Changed 5 years ago by andrew.mathas

Replying to tscrim:

Replying to andrew.mathas:

I'm +1 for getting things closer to the KLR algebra (something that I hope to eventually get into Sage at some point). Otherwise I don't have an opinion on which presentation we use. How much would have to be changed in order to move to the Hu-Mathas presentation?

With all of these things it is mainly a matter of implementing appropriate analogues of the three methods _product_LTwTv, _product_Tw_L, and _Li_power that underpin the multiplication. Replacing q with a two variable version may be the hardest option as we'd have to think what the appropriate normalisation of the Jucys-Murphy elements is. This said, I would prefer to have the more symmetric relations (T_i-q)(T_i+q^{-1})=0, so I will have a think about this.

Regarding KLR algebras, implementing the "affine" KLR algebras is reasonably straightforward. I know now of a way to do the cyclotomic quotients in a few cases and I will implement them at some point, although the isomorphism to the ungraded algebras is much harder to do.

comment:12 in reply to: ↑ 11 Changed 5 years ago by tscrim

Replying to andrew.mathas:

Replying to tscrim:

Replying to andrew.mathas:

I'm +1 for getting things closer to the KLR algebra (something that I hope to eventually get into Sage at some point). Otherwise I don't have an opinion on which presentation we use. How much would have to be changed in order to move to the Hu-Mathas presentation?

With all of these things it is mainly a matter of implementing appropriate analogues of the three methods _product_LTwTv, _product_Tw_L, and _Li_power that underpin the multiplication. Replacing q with a two variable version may be the hardest option as we'd have to think what the appropriate normalisation of the Jucys-Murphy elements is. This said, I would prefer to have the more symmetric relations (T_i-q)(T_i+q^{-1})=0, so I will have a think about this.

I believe I've said this above, but to be pedantic, I have no preference as to what quadratic relation is. How much could be obtained by looking at the affine Hecke algebra and passing to the quotient?

Regarding KLR algebras, implementing the "affine" KLR algebras is reasonably straightforward. I know now of a way to do the cyclotomic quotients in a few cases and I will implement them at some point, although the isomorphism to the ungraded algebras is much harder to do.

Please cc me on that ticket when you create it. I would be happy to review it.

comment:13 Changed 4 years ago by git

  • Commit changed from e9b6a594ae1e089b51b37081f35743402447a960 to f39c1399357d574109fb152cf456d8690fadde1b

Branch pushed to git repo; I updated commit sha1. New commits:

abe8764Merge branch 'public/algebras/ariki_koike_algebras-20469' of trac.sagemath.org:sage into public/algebras/ariki_koike_algebras-20469
0345a42Merge branch 'develop' into public/algebras/ariki_koike_algebras-20469
0ec4023Merge branch 'develop' into public/algebras/ariki_koike_algebras-20469
f39c139Merge branch 'develop' into public/algebras/ariki_koike_algebras-20469

comment:14 Changed 4 years ago by tscrim

  • Milestone changed from sage-7.3 to sage-8.1

comment:15 Changed 4 years ago by git

  • Commit changed from f39c1399357d574109fb152cf456d8690fadde1b to 738616df7442862e6062c78d5120e641b9461ebf

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

738616dMerge commit 'e9b6a594ae1e089b51b37081f35743402447a960' into public/algebras/ariki_koike_algebras-20469_2

comment:16 Changed 3 years ago by git

  • Commit changed from 738616df7442862e6062c78d5120e641b9461ebf to 08f90379eeb5ccb670d36e3cdbed2c07cdc78068

Branch pushed to git repo; I updated commit sha1. New commits:

21b9e6bMerge branch 'public/algebras/ariki_koike_algebras-20469' of git://trac.sagemath.org/sage into public/algebras/ariki_koike_algebras-20469
08f9037Fixing bugs and minor cleanup.

comment:17 Changed 3 years ago by tscrim

I've found and fixed 2 bugs with the multiplication:

  1. In _product_LTwTv, the coefficient c was not being multiplied in the second term.
  2. In _Li_power, the formula was suppose to be q-1 (q - 1) = 1 - q-1, but instead it was q - q-1. This fixes the associativity test.

Now all doctests are currently passing.

comment:18 Changed 3 years ago by git

  • Commit changed from 08f90379eeb5ccb670d36e3cdbed2c07cdc78068 to a6c89080e871eac1ab7d67d12855aee00d3183d3

Branch pushed to git repo; I updated commit sha1. New commits:

7eafefdFinished initial pass of cleanup.
f074dadSome multiplication optimizations by not creating as many transient elements.
a6c8908A little bit more touchups and cosmetic changes.

comment:19 Changed 3 years ago by tscrim

  • Milestone changed from sage-8.1 to sage-8.3
  • Status changed from new to needs_review

Here is a version with 2 bases: the T basis given by BM and LT basis given by AK.

From some testing, the T basis implementation is (currently) clearly the better basis:

sage: def test(B):
....:     for b in B:
....:         for bp in B:
....:             b * bp
....:             
sage: H = algebras.ArikiKoike(3, 3)
sage: LT = H.LT()
sage: T = H.T()
sage: %time test(LT.basis())
CPU times: user 4min 30s, sys: 1.64 s, total: 4min 31s
Wall time: 4min 31s
sage: %time test(T.basis())
CPU times: user 1min 40s, sys: 739 ms, total: 1min 41s
Wall time: 1min 40s

In particular, this LT basis computation took over 5GB of RAM, whereas the T basis computation took less than 2GB. (The computation above involves all 26244 possible products.) The speed difference also holds for smaller dimensional spaces.

comment:20 Changed 3 years ago by tscrim

  • Keywords days93.51 added

comment:21 Changed 3 years ago by tscrim

  • Branch changed from public/algebras/ariki_koike_algebras-20469 to public/algebras/ariki_koike_algebras_with_bases-20469
  • Commit changed from a6c89080e871eac1ab7d67d12855aee00d3183d3 to 6d1ac2c8f1e94ff3483b5f66182c43d061aec22b

Last 10 new commits:

429b0f9Fixing an error with multiplication of the T_i generators.
7317e86Fixing multiplication the other way.
c504826Initial review
21822a2Rewriting product code to avoid recursion
f366691Fixing bugs and minor cleanup.
3af6dccFinished initial pass of cleanup.
59d9583Some multiplication optimizations by not creating as many transient elements.
3e94feaA little bit more touchups and cosmetic changes.
1d92cb7Implementation of T basis following [BM1997]_.
6d1ac2cUse cartesian_product as the indices for the basis.

comment:22 Changed 3 years ago by git

  • Commit changed from 6d1ac2c8f1e94ff3483b5f66182c43d061aec22b to 712a76a071c1910f8f102f179e47cf43cb770146

Branch pushed to git repo; I updated commit sha1. New commits:

712a76aFixing documentation.

comment:23 Changed 3 years ago by git

  • Commit changed from 712a76a071c1910f8f102f179e47cf43cb770146 to 829576c0e9f6136a0f921e9c69a49e1a5c087307

Branch pushed to git repo; I updated commit sha1. New commits:

829576cRemoving duplicate reference.

comment:24 Changed 3 years ago by git

  • Commit changed from 829576c0e9f6136a0f921e9c69a49e1a5c087307 to c8a9c2f468c6832750ba0898257fab53e7996192

Branch pushed to git repo; I updated commit sha1. New commits:

c8a9c2fLast little tweaks to the documentation.

comment:25 Changed 3 years ago by vdelecroix

  • Milestone changed from sage-8.3 to sage-8.4

update milestone 8.3 -> 8.4

comment:26 Changed 3 years ago by chapoton

some typos:

OUPTUT
These element different by a power of `q` from the corresponding
an tuple

missing \ in

+.. [BM1997] K. Bremke and G. Malle,

comment:27 Changed 3 years ago by chapoton

  • Status changed from needs_review to needs_work

branch is red

comment:28 Changed 3 years ago by git

  • Commit changed from c8a9c2f468c6832750ba0898257fab53e7996192 to ebb2c1b6ac2f6efa06cc76e3ce7fc55ff0be2e05

Branch pushed to git repo; I updated commit sha1. New commits:

ebb2c1bMerge branch 'public/algebras/ariki_koike_algebras_with_bases-20469' in 8.5.b6

comment:29 Changed 3 years ago by git

  • Commit changed from ebb2c1b6ac2f6efa06cc76e3ce7fc55ff0be2e05 to 0a058b5ee014946497148939e53e6ffc9ecba67a

Branch pushed to git repo; I updated commit sha1. New commits:

0a058b5one detail

comment:30 Changed 3 years ago by chapoton

  • Milestone changed from sage-8.4 to sage-8.5
  • Status changed from needs_work to needs_review

comment:31 Changed 3 years ago by chapoton

  • Status changed from needs_review to needs_work

one failing doctest, see patchbot

Last edited 3 years ago by chapoton (previous) (diff)

comment:32 Changed 19 months ago by git

  • Commit changed from 0a058b5ee014946497148939e53e6ffc9ecba67a to 5aac3c21109cee43d1382e2d6ef04839b73e7b64

Branch pushed to git repo; I updated commit sha1. New commits:

82da4c4Merge branch 'public/algebras/ariki_koike_algebras_with_bases-20469' of git://trac.sagemath.org/sage into public/algebras/ariki_koike_algebras_with_bases-20469
5aac3c2Fixing multiplication in the T basis. Other misc cleanup.

comment:33 Changed 19 months ago by tscrim

  • Status changed from needs_work to needs_review

Thanks to Sebastian doing some very thorough testing in looking at changing the index set, I came across a subtle bug in the T multiplication. When performing the reduction of the T0r in Tk,a, we can have a T00, which we want to "represent" as Tk,0, but this is defined as 1. So we have lost track of the sk-1 ... s1 permutation. This has now been fixed.

comment:34 Changed 19 months ago by chapoton

There seems to be some missing r""" that cause 3 "invalid escape sequences", see patchbot report.

comment:35 Changed 19 months ago by git

  • Commit changed from 5aac3c21109cee43d1382e2d6ef04839b73e7b64 to 9a12b94c1a28b60baa0d4d5b9fb91529d49cd82f

Branch pushed to git repo; I updated commit sha1. New commits:

9a12b94Making things raw strings to fix invalid escape sequences.

comment:36 Changed 19 months ago by tscrim

Thanks. Fixed.

comment:37 follow-up: Changed 19 months ago by soehms

It seems that you missed to fix this:

sage: H = algebras.ArikiKoike(3, 4)
sage: LT = H.LT()
sage: LT.inject_variables()
Defining L1, L2, L3, L4, T1, T2, T3
sage: LT._Li_power(2,4) == L2 * LT._Li_power(2,3)
False

comment:38 in reply to: ↑ 37 ; follow-up: Changed 19 months ago by tscrim

Replying to soehms:

It seems that you missed to fix this:

sage: H = algebras.ArikiKoike(3, 4)
sage: LT = H.LT()
sage: LT.inject_variables()
Defining L1, L2, L3, L4, T1, T2, T3
sage: LT._Li_power(2,4) == L2 * LT._Li_power(2,3)
False

I do not think there is need to fix that because _Li_power is only used in the internal multiplication, which ultimately cancels or resolves out the issues with not doing proper reduction of the the Lik. By not doing as many resolutions (which can generate large number of terms), it should be faster. Should I add something to the _Li_power docstring about this or run some timings to confirm?

comment:39 in reply to: ↑ 38 Changed 19 months ago by soehms

Replying to tscrim:

Replying to soehms:

It seems that you missed to fix this:

sage: H = algebras.ArikiKoike(3, 4)
sage: LT = H.LT()
sage: LT.inject_variables()
Defining L1, L2, L3, L4, T1, T2, T3
sage: LT._Li_power(2,4) == L2 * LT._Li_power(2,3)
False

I do not think there is need to fix that because _Li_power is only used in the internal multiplication, which ultimately cancels or resolves out the issues with not doing proper reduction of the the Lik. By not doing as many resolutions (which can generate large number of terms), it should be faster.

Ah, I forgot about that explanation!

Should I add something to the _Li_power docstring about this or run some timings to confirm?

I think a comment on that would make sense, since LT._Li_power(2,4) == L2**4 giving False is quite irritating.

comment:40 Changed 19 months ago by git

  • Commit changed from 9a12b94c1a28b60baa0d4d5b9fb91529d49cd82f to ff1ad8647d1bca65f348db804383a71c39e2b724

Branch pushed to git repo; I updated commit sha1. New commits:

ff1ad86A hybrid approach to an _Li_power computation.

comment:41 follow-up: Changed 19 months ago by tscrim

I ran some timings to confirm my suspicions, and here is what I found:

sage: def test(LT):
....:     B = LT.basis()
....:     for b in B:
....:         for bp in B:
....:             dummy = b * bp
sage: H = algebras.ArikiKoike(4, 2)
sage: LT = H.LT()
sage: %time test(LT)
CPU times: user 3.49 s, sys: 6.16 ms, total: 3.5 s
Wall time: 3.5 s
sage: H = algebras.ArikiKoike(5, 2)
sage: LT = H.LT()
sage: %time test(LT)
CPU times: user 2min 50s, sys: 446 ms, total: 2min 51s
Wall time: 2min 51s

versus always resolving it out:

sage: H = algebras.ArikiKoike(4, 2)
sage: LT = H.LT()
sage: %time test(LT)
CPU times: user 3.16 s, sys: 23.5 ms, total: 3.18 s
Wall time: 3.18 s
sage: H = algebras.ArikiKoike(5, 2)
sage: LT = H.LT()
sage: %time test(LT)
CPU times: user 3min 14s, sys: 463 ms, total: 3min 14s
Wall time: 3min 14s

So it seems to be inconsistent with which one is better strangely enough. Memory-wise they seem to be similar. The latter is ~11% slower. So I implemented a hybrid approach and here is the timings for that:

sage: H = algebras.ArikiKoike(4, 2)
sage: LT = H.LT()
sage: %time test(LT)
CPU times: user 3.27 s, sys: 25.4 ms, total: 3.29 s
Wall time: 3.33 s
sage: H = algebras.ArikiKoike(5, 2)
sage: LT = H.LT()
sage: %time test(LT)
CPU times: user 3min 17s, sys: 389 ms, total: 3min 17s
Wall time: 3min 17s

So I think I will go with the hybrid, trying keep some of the benefits of both (less multiplication and strict correctness at intermediate steps). I suspect the last timing is a little skewed because I was doing a few other things on my computer at the time.

comment:42 in reply to: ↑ 41 ; follow-up: Changed 19 months ago by soehms

Replying to tscrim:

So I think I will go with the hybrid, trying keep some of the benefits of both (less multiplication and strict correctness at intermediate steps). I suspect the last timing is a little skewed because I was doing a few other things on my computer at the time.

Are you sure you want to keep the hybrid version? I repeated your test and the timing comparison was even worse.

What about the following suggestion: Rename _Li_power as something like _prepare_Li_power to avoid such irritation. In addition, leave your new test in the docstring returning False as an example that this method does not give the final result (but for this purpose you have to run it for algebras.ArikiKoike(3, 4)).

Furthermore, the local function L in _Li_power seems not to be used any more. Can't we delete it?

comment:43 in reply to: ↑ 42 ; follow-up: Changed 19 months ago by tscrim

Replying to soehms:

Replying to tscrim:

So I think I will go with the hybrid, trying keep some of the benefits of both (less multiplication and strict correctness at intermediate steps). I suspect the last timing is a little skewed because I was doing a few other things on my computer at the time.

Are you sure you want to keep the hybrid version? I repeated your test and the timing comparison was even worse.

Which timings? I agree this will probably be worse than the previous version, but it cannot be worse than the fully-reduced-to-basis version.

What about the following suggestion: Rename _Li_power as something like _prepare_Li_power to avoid such irritation. In addition, leave your new test in the docstring returning False as an example that this method does not give the final result (but for this purpose you have to run it for algebras.ArikiKoike(3, 4)).

I think that name is less descriptive. Plus it gives the correct result, just not necessarily in the basis elements, which is okay for an internal function not visible to the standard user. So if we decide revert the change, then I think just a warning would be sufficient.

Furthermore, the local function L in _Li_power seems not to be used any more. Can't we delete it?

Yes, we can delete it.

comment:44 in reply to: ↑ 43 ; follow-up: Changed 19 months ago by soehms

Replying to tscrim:

Which timings? I agree this will probably be worse than the previous version, but it cannot be worse than the fully-reduced-to-basis version.

Of course, I meant in the comparison with the previous version!

So if we decide revert the change, then I think just a warning would be sufficient.

Agreed!

Once this is done from my point of view we can let the ticket pass.

comment:45 Changed 19 months ago by git

  • Commit changed from ff1ad8647d1bca65f348db804383a71c39e2b724 to 2e11e63d49686fc133ddfb221f01cbb6f8e67f50

Branch pushed to git repo; I updated commit sha1. New commits:

2e11e63Reverting to original method for _Li_power and added warning.

comment:46 in reply to: ↑ 44 ; follow-up: Changed 19 months ago by tscrim

Replying to soehms:

Replying to tscrim:

So if we decide revert the change, then I think just a warning would be sufficient.

Agreed!

Once this is done from my point of view we can let the ticket pass.

Done. Thank you! Please set to a final positive review if you are happy with my changes.

comment:47 Changed 19 months ago by git

  • Commit changed from 2e11e63d49686fc133ddfb221f01cbb6f8e67f50 to bbe4874c2e1b013020de51553be87b2448767cc4

Branch pushed to git repo; I updated commit sha1. New commits:

ed667ccMerge branch 'public/algebras/ariki_koike_algebras_with_bases-20469' of git://trac.sagemath.org/sage into ariki_koike_alg_20469
bbe487420469: fixed pyflakes hint

comment:48 in reply to: ↑ 46 Changed 19 months ago by soehms

  • Reviewers changed from Andrew Mathas, Travis Scrimshaw to Andrew Mathas, Travis Scrimshaw, Sebastian Oehms
  • Status changed from needs_review to positive_review

Replying to tscrim:

Done. Thank you! Please set to a final positive review if you are happy with my changes.

Yes, I am (just fixed a patchbot hint)! Thanks, as well.

comment:49 Changed 19 months ago by git

  • Commit changed from bbe4874c2e1b013020de51553be87b2448767cc4 to daf777ec27554610ab39c5bbe31f74673238c58c
  • Status changed from positive_review to needs_review

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

daf777e20469: redundant local function `L` deleted

comment:50 Changed 19 months ago by tscrim

  • Status changed from needs_review to positive_review

Thank you.

comment:51 Changed 19 months ago by tscrim

  • Milestone changed from sage-8.5 to sage-9.1

comment:52 Changed 19 months ago by vbraun

  • Branch changed from public/algebras/ariki_koike_algebras_with_bases-20469 to daf777ec27554610ab39c5bbe31f74673238c58c
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.