Opened 3 years ago
Closed 3 years ago
#27451 closed enhancement (fixed)
speedup of induced trivial character basis
Reported by: | zabrocki | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-8.7 |
Component: | combinatorics | Keywords: | sf, combinat |
Cc: | Merged in: | ||
Authors: | Mike Zabrocki | Reviewers: | Travis Scrimshaw, Frédéric Chapoton |
Report Upstream: | N/A | Work issues: | |
Branch: | eb81438 (Commits, GitHub, GitLab) | Commit: | eb81438e35877f464266b706a1e63d75701adcd6 |
Dependencies: | Stopgaps: |
Description
Replace the recursive implementation of the induced trivial character basis with an explicit formula that runs a bit faster. Additional minor improvements to the documentation of character.py.
Change History (14)
comment:1 Changed 3 years ago by
- Branch set to public/combinat/induced_trivial_speedup-27451
- Commit set to 894814475aab0b1070605a14f258b75c9e3869ff
comment:2 Changed 3 years ago by
With speedup:
sage: time ht(s[5,4,3,2,1]) CPU times: user 42.8 s, sys: 199 ms, total: 43 s sage: time s(ht[5,4,3,2,1]) CPU times: user 2.34 s, sys: 106 ms, total: 2.45 s
Without:
sage: time ht(s[5,4,2,1]) # larger test takes too long CPU times: user 1min 56s, sys: 597 ms, total: 1min 57s sage: time s(ht[5,4,3,2,1]) CPU times: user 2min 37s, sys: 617 ms, total: 2min 38s
comment:3 Changed 3 years ago by
- Commit changed from 894814475aab0b1070605a14f258b75c9e3869ff to c37a754a05cc2f87b18661fd740ab183a21d3086
Branch pushed to git repo; I updated commit sha1. New commits:
c37a754 | kronecker -> Kronecker
|
comment:4 Changed 3 years ago by
- Status changed from new to needs_review
The speedup is probably minor (but still significant) for symmetric functions of smaller degree, but major for larger degree.
For a smaller degree example: with:
sage: time s(ht[3,2]) CPU times: user 96 ms, sys: 13.5 ms, total: 110 ms Wall time: 101 ms sage: time ht(s[3,2]) CPU times: user 112 ms, sys: 16.9 ms, total: 128 ms Wall time: 117 ms
without:
sage: time s(ht[3,2]) CPU times: user 158 ms, sys: 25.2 ms, total: 183 ms Wall time: 167 ms sage: time ht(s[3,2]) CPU times: user 202 ms, sys: 35.3 ms, total: 238 ms Wall time: 213 ms
comment:5 Changed 3 years ago by
That is quite an improvement.
I have one recommendation, you should replace
-p.sum(c*elt for c,elt in foo) +p.linear_combination((elt, c) for c,elt in foo)
as the latter has less transient elements because it does not compute the scalar multiplication on each element. At least, I expect some additional speedup by doing that.
Some nitpicks:
Add back in this period:
- The coercions are set up between the ``other_basis``. + The coercions are set up between the ``other_basis``
I think this would make it a little easier to read the (non-compiled) doc:
- \sum_{j=0}^r (-1)^{r-j}k^j\binom{r,j} \left( - \frac{1}{k} \sum_{d|k} \mu(d/k) p_d \right)_k. + \sum_{j=0}^r (-1)^{r-j}k^j\binom{r,j} + \left( \frac{1}{k} \sum_{d|k} \mu(d/k) p_d \right)_k.
Feel free to ignore this.
Missing comma:
-For a partition `\gamma = (1^{m_1}, 2^{m_2}, \ldots r^{m_r})`, +For a partition `\gamma = (1^{m_1}, 2^{m_2}, \ldots, r^{m_r})`,
I don't know how mathjax handles the nonbreaking space \right)_k~.
. You are also not doing it consistently between _b_bar_power_k_r
and _b_bar_power_gamma
.
I believe this looks better in the doc:
-\sum_{\gamma} \left< h_\lambda, p_\gamma \right> +\sum_{\gamma} \left\langle h_\lambda, p_\gamma \right\rangle
comment:6 Changed 3 years ago by
- Commit changed from c37a754a05cc2f87b18661fd740ab183a21d3086 to 3f847de479a04a2909cfeca77f9d3b2f9322f4df
Branch pushed to git repo; I updated commit sha1. New commits:
3f847de | sum to linear_combination, two corrections on doc
|
comment:7 Changed 3 years ago by
- Commit changed from 3f847de479a04a2909cfeca77f9d3b2f9322f4df to 4823389dd118642160f679158e509b489b659f96
Branch pushed to git repo; I updated commit sha1. New commits:
4823389 | couple more changes to the doc strings
|
comment:8 Changed 3 years ago by
- please use capital M for Moebius in the doc (at several places)
- rather use
k // d
thank/d
in_b_power_k
and
comment:9 Changed 3 years ago by
- Status changed from needs_review to needs_work
plus one failing doctest in
sage -t --long src/sage/categories/sets_cat.py
comment:10 Changed 3 years ago by
- Commit changed from 4823389dd118642160f679158e509b489b659f96 to eb81438e35877f464266b706a1e63d75701adcd6
Branch pushed to git repo; I updated commit sha1. New commits:
eb81438 | corrections to doc
|
comment:11 Changed 3 years ago by
- Status changed from needs_work to needs_review
I think that I got the changes and all doc tests pass. Thanks for all the suggestions.
comment:12 Changed 3 years ago by
- Reviewers set to Travis Scrimshaw, Frédéric Chapoton
Thanks Mike. If the patchbot comes back green, then positive review.
comment:13 Changed 3 years ago by
- Status changed from needs_review to positive_review
comment:14 Changed 3 years ago by
- Branch changed from public/combinat/induced_trivial_speedup-27451 to eb81438e35877f464266b706a1e63d75701adcd6
- Resolution set to fixed
- Status changed from positive_review to closed
I ran into a speed block using this basis recently and realized that the reason was the explicit formula in terms of the power sum was not implemented. Speed tests to come.
New commits:
delete generic implementation and replace with explicit