Skip to content

Conversation

tscrim
Copy link
Collaborator

@tscrim tscrim commented Apr 11, 2024

Since we are going to work with a matrix $f^{\lambda} \times f^{\lambda}$ (recall $f^{\lambda}$ is the number of standard Young tableaux of shape $\lambda$), then we should just store the list of standard tableaux rather than iterating over them repeatedly. This results in a major speedup:

sage: from sage.combinat.specht_module import simple_module_rank
sage: %time simple_module_rank([5,3,2], GF(2))
CPU times: user 1.34 s, sys: 35.7 ms, total: 1.38 s
Wall time: 1.38 s
200

versus before

sage: %time simple_module_rank([5,3,2], GF(2))
CPU times: user 4.97 s, sys: 65 ms, total: 5.03 s
Wall time: 5.06 s
200

📝 Checklist

  • The title is concise and informative.
  • The description explains in detail what this PR is about.
  • I have linked a relevant issue or discussion.
  • I have created tests covering the changes.
  • I have updated the documentation accordingly.

⌛ Dependencies

@tscrim
Copy link
Collaborator Author

tscrim commented Apr 11, 2024

Some very simple, but useful optimizations. Should be an easy review. @darijgr @fchapoton @AndrewMathas, if you have time.

Copy link
Contributor

@darijgr darijgr left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Yep, good change. LGTM

@tscrim
Copy link
Collaborator Author

tscrim commented Apr 11, 2024

Thank you. I will let the tests run then change to a positive review, but I doubt anything will fail.

Copy link

Documentation preview for this PR (built with commit 19d6ce3; changes) is ready! 🎉

vbraun pushed a commit to vbraun/sage that referenced this pull request Apr 20, 2024
sagemathgh-37784: Speed up symmetric group simple_module_rank()
    
<!-- ^ Please provide a concise and informative title. -->
<!-- ^ Don't put issue numbers in the title, do this in the PR
description below. -->
<!-- ^ For example, instead of "Fixes sagemath#12345" use "Introduce new method
to calculate 1 + 2". -->
<!-- v Describe your changes below in detail. -->
<!-- v Why is this change required? What problem does it solve? -->
<!-- v If this PR resolves an open issue, please link to it here. For
example, "Fixes sagemath#12345". -->

Since we are going to work with a matrix $f^{\lambda} \times
f^{\lambda}$ (recall $f^{\lambda}$ is the number of standard Young
tableaux of shape $\lambda$), then we should just store the list of
standard tableaux rather than iterating over them repeatedly. This
results in a major speedup:
```
sage: from sage.combinat.specht_module import simple_module_rank
sage: %time simple_module_rank([5,3,2], GF(2))
CPU times: user 1.34 s, sys: 35.7 ms, total: 1.38 s
Wall time: 1.38 s
200
```
versus before
```
sage: %time simple_module_rank([5,3,2], GF(2))
CPU times: user 4.97 s, sys: 65 ms, total: 5.03 s
Wall time: 5.06 s
200
```

### 📝 Checklist

<!-- Put an `x` in all the boxes that apply. -->

- [x] The title is concise and informative.
- [x] The description explains in detail what this PR is about.
- [x] I have linked a relevant issue or discussion.
- [x] I have created tests covering the changes.
- [x] I have updated the documentation accordingly.

### ⌛ Dependencies

<!-- List all open PRs that this PR logically depends on. For example,
-->
<!-- - sagemath#12345: short description why this is a dependency -->
<!-- - sagemath#34567: ... -->
    
URL: sagemath#37784
Reported by: Travis Scrimshaw
Reviewer(s): Darij Grinberg
@vbraun vbraun merged commit fbb9919 into sagemath:develop Apr 27, 2024
@tscrim tscrim deleted the combinat/faster_simple_module_rank branch April 28, 2024 08:33
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging this pull request may close these issues.

4 participants