speedup of induced trivial character basis

[zabrocki]

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.

[zabrocki]

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:

​8948144

delete generic implementation and replace with explicit

[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

[git]

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

​c37a754

kronecker -> Kronecker

[zabrocki]

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

[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

[git]

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

​3f847de

sum to linear_combination, two corrections on doc

[git]

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

​4823389

couple more changes to the doc strings

[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

[chapoton]

plus one failing doctest in

sage -t --long src/sage/categories/sets_cat.py

[git]

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

​eb81438

corrections to doc

[zabrocki]

I think that I got the changes and all doc tests pass. Thanks for all the suggestions.

[tscrim]

Thanks Mike. If the patchbot comes back green, then positive review.