Opened 15 months ago
Closed 15 months ago
#27451 closed enhancement (fixed)
speedup of induced trivial character basis
Reported by:  zabrocki  Owned by:  

Priority:  major  Milestone:  sage8.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)  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 15 months ago by
 Branch set to public/combinat/induced_trivial_speedup27451
 Commit set to 894814475aab0b1070605a14f258b75c9e3869ff
comment:2 Changed 15 months 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 15 months 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 15 months 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 15 months 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 (noncompiled) doc:
 \sum_{j=0}^r (1)^{rj}k^j\binom{r,j} \left(  \frac{1}{k} \sum_{dk} \mu(d/k) p_d \right)_k. + \sum_{j=0}^r (1)^{rj}k^j\binom{r,j} + \left( \frac{1}{k} \sum_{dk} \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 15 months 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 15 months 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 15 months 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 15 months 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 15 months 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 15 months 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 15 months 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 15 months ago by
 Status changed from needs_review to positive_review
comment:14 Changed 15 months ago by
 Branch changed from public/combinat/induced_trivial_speedup27451 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