#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) 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 zabrocki

  • Branch set to public/combinat/induced_trivial_speedup-27451
  • Commit set to 894814475aab0b1070605a14f258b75c9e3869ff

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:

8948144delete generic implementation and replace with explicit

comment:2 Changed 15 months ago by zabrocki

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 git

  • Commit changed from 894814475aab0b1070605a14f258b75c9e3869ff to c37a754a05cc2f87b18661fd740ab183a21d3086

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

c37a754kronecker -> Kronecker

comment:4 Changed 15 months ago by zabrocki

  • 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 tscrim

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 15 months ago by git

  • Commit changed from c37a754a05cc2f87b18661fd740ab183a21d3086 to 3f847de479a04a2909cfeca77f9d3b2f9322f4df

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

3f847desum to linear_combination, two corrections on doc

comment:7 Changed 15 months ago by git

  • Commit changed from 3f847de479a04a2909cfeca77f9d3b2f9322f4df to 4823389dd118642160f679158e509b489b659f96

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

4823389couple more changes to the doc strings

comment:8 Changed 15 months ago by chapoton

  • please use capital M for Moebius in the doc (at several places)
  • rather use k // d than k/d in _b_power_k and

comment:9 Changed 15 months ago by chapoton

  • 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 git

  • Commit changed from 4823389dd118642160f679158e509b489b659f96 to eb81438e35877f464266b706a1e63d75701adcd6

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

eb81438corrections to doc

comment:11 Changed 15 months ago by zabrocki

  • 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 tscrim

  • 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 tscrim

  • Status changed from needs_review to positive_review

comment:14 Changed 15 months ago by vbraun

  • Branch changed from public/combinat/induced_trivial_speedup-27451 to eb81438e35877f464266b706a1e63d75701adcd6
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.