Opened 10 years ago

Closed 10 years ago

Last modified 6 years ago

#14461 closed enhancement (fixed)

Change the method cardinality to StandardTableaux of fixed size

Reported by: Grégory Châtel Owned by: Sage Combinat CC user
Priority: major Milestone: sage-5.10
Component: combinatorics Keywords: tableau, cardinality
Cc: Sage Combinat CC user Merged in: sage-5.10.beta0
Authors: Grégory Châtel Reviewers: Travis Scrimshaw, Mike Hansen
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by Travis Scrimshaw)

Change the method cardinality in the class StandardTableaux_size

Before:

sage: timeit('StandardTableaux(8).cardinality()')
125 loops, best of 3: 3.53 ms per loop
sage: timeit('StandardTableaux(10).cardinality()')
125 loops, best of 3: 7.58 ms per loop
sage: timeit('StandardTableaux(12).cardinality()')
25 loops, best of 3: 15.5 ms per loop

With the patch:

sage: timeit('StandardTableaux(8).cardinality()') 
625 loops, best of 3: 119 µs per loop
sage: timeit('StandardTableaux(10).cardinality()')
625 loops, best of 3: 136 µs per loop
sage: timeit('StandardTableaux(12).cardinality()')
625 loops, best of 3: 153 µs per loop
sage: timeit('StandardTableaux(50).cardinality()')
625 loops, best of 3: 642 µs per loop

Apply:

Attachments (3)

cardinality_for_standard_tableaux-gc.patch (3.6 KB) - added by Grégory Châtel 10 years ago.
trac_14461-cardinality_standard_tableaux-review-ts.patch (943 bytes) - added by Travis Scrimshaw 10 years ago.
trac_14461-review-mh.patch (3.5 KB) - added by Mike Hansen 10 years ago.

Download all attachments as: .zip

Change History (18)

comment:1 Changed 10 years ago by Grégory Châtel

Status: newneeds_review

comment:2 Changed 10 years ago by Grégory Châtel

Description: modified (diff)

comment:3 Changed 10 years ago by Travis Scrimshaw

Hey,

Could you make the following changes:

  • describe the algorithm that you are using the doc,
  • add a test to show that your computation agrees with the constructed number (for some smaller n than 50 of course),
  • put your (real) name in the trac authors section.

Thanks,
Travis

Last edited 10 years ago by Travis Scrimshaw (previous) (diff)

comment:4 Changed 10 years ago by Grégory Châtel

Authors: Grégory Chatel

Here is a new version of my patch with tests. Sorry, I'm not a native speaker and this would my first contribution.

Instead of using hook formula on every shape of Young tableau my algorithm counts the number of involution of size n which are in bijection with standard tableau of size n.

Sage seems do be limited around size 35 :

sage: timeit('StandardTableaux(35).cardinality()')
5 loops, best of 3: 5.83 s per loop

With the patch

sage: timeit('StandardTableaux(35).cardinality()')         
625 loops, best of 3: 390 µs per loop

Changed 10 years ago by Grégory Châtel

comment:5 Changed 10 years ago by Travis Scrimshaw

Reviewers: Travis Scrimshaw

Hey Gregory,

This is a great speedup, and I was surprised that involutions, or at least counting them, is not currently in Sage (there must surely be a ticket for this...). Anyways, I've uploaded a review patch which adds the description of the cardinality. If you are happy with the changes, feel free to set this to positive review.

Best,
Travis

In case you are unaware, to check you should apply my review patch after yours, run sage -b, then run sage -docbuild reference/combinat html and look at your (local) documentation. Feel free to ask me questions if you need to.

comment:6 Changed 10 years ago by Mike Hansen

Heh, I just added my own review patch (on top of the original, not yours). I added a reference to Fulton's Young Tableaux as well as made some minor changes. These give about a 3x speedup on the original (new) implementation. I also didn't test nearly as many values since it adds like an extra 3 seconds to the files tests.

comment:7 Changed 10 years ago by Travis Scrimshaw

Reviewers: Travis ScrimshawTravis Scrimshaw, Mike Hansen

Hey Mike,

I'll merge your review patch with some of my doc additions and repost that (especially since you get a 3x speedup). Should be up within 15 minutes.

Changed 10 years ago by Travis Scrimshaw

comment:8 Changed 10 years ago by Travis Scrimshaw

Description: modified (diff)

Hey Mike,

I've tweaked my review patch to apply after yours. If your happy with my changes, then you can set this to positive review.

Thanks,
Travis

comment:9 Changed 10 years ago by Mike Hansen

Status: needs_reviewpositive_review

Looks good.

comment:10 Changed 10 years ago by Travis Scrimshaw

Thanks Mike. Thanks Gregory, and welcome to the sage development community.

comment:11 Changed 10 years ago by Mike Hansen

I just updated the reference for Fulton's Young Tableaux.

comment:12 Changed 10 years ago by Jeroen Demeyer

Status: positive_reviewneeds_work

trac_14461-review-mh.patch needs a proper commit message.

Changed 10 years ago by Mike Hansen

Attachment: trac_14461-review-mh.patch added

comment:13 Changed 10 years ago by Mike Hansen

Status: needs_workpositive_review

Done

comment:14 Changed 10 years ago by Jeroen Demeyer

Merged in: sage-5.10.beta0
Resolution: fixed
Status: positive_reviewclosed

comment:15 Changed 6 years ago by Frédéric Chapoton

Authors: Grégory ChatelGrégory Châtel
Note: See TracTickets for help on using tickets.