Involutions on NSym and QSym part II

[darij]

This continues #15476. It is not my last word on NSym (I'm still planning to implement Eulerian and other idempotents -- but this is waiting on the merge of #15650 and not much of a priority anyway).

The following has been implemented:

• the omega involution on NSym and QSym (and alternative syntaxes for that on Sym);
  
• fixes on some NSym and QSym methods to return values in correct parents;
  
• Verschiebung on the elementary basis of NSym (it would formerly use coercion for that, but there's a simple formula);
  
• a way to compute the internal product on the Psi basis of NSym (which is very fast if the compositions have small length, but otherwise is quite wasteful -- hence not made a default);
  
• immaculate functions in NSym indexed by arbitrary integer vectors (not just compositions);
  
• the reduced Kronecker product (formerly in #15825, now moved here and fixed);
  
• an analogue thereof (but not a lift) on NSym;
  
• the t-completion of a partition (formerly in #15825);
  
• improvements on the to_dyck_word method on partitions (formerly in #15825).

[git]

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

​fea1743

left-padded Kronecker product on Sym too, and fixes for my own bugs:

[git]

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

​bff955a

more bugfixes

[git]

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

​f082858	Merge branch 'public/combinat/invol-nsym-2' of trac.sagemath.org:sage into public/combinat/invol-nsym-2
​c98d300	Review changes and (minor) optimizations.

[tscrim]

Hey Darij,

I've made some review changes, (minor) optimizations, and rewrote the algorithm for the internal product from bracketing using a backtracing² algorithm. Please check that it is faster than the old one (I'm guessing you already have some timings...but I will run some later) and you decide if you want to make it the main call for internal product or not. Otherwise if you're happy with my changes, pos_rev.

Best,
Travis

[darij]

Thank you! I've looked at all changes apart from the internal product one, for which I'll need some more concentration than I have right now (writing a paper on QSym of all things); I've also added a few more optimizations.

Observations:

1. for m, c in self.monomial_coefficients().items() is indeed slower than for m, c in self (thanks for making me aware of this!), but for m, c in self.monomial_coefficients().iteritems() is not (although the difference is very small). I still prefer for m, c in self for brevity, but where the iteritems syntax was used I've put it back.

2. The global sum function is waaaay slower than sum methods on specific free modules, even if the parent has to be identified first in order to call the latter. And this is even without our horrible hijacked sum function in the console (#9321, #15163).

[git]

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

​31271df	Merge branch 'public/combinat/invol-nsym-2' of git://trac.sagemath.org/sage into nsym
​262bea1	Merge branch 'public/combinat/invol-nsym-2' of git://trac.sagemath.org/sage into nsym
​a9c74b4	more optimizations

[darij]

BTW sorry for the two merge commits. It looks like both you and I merged our own NSym branches with 6.2.beta5 first and then we had to merge our merges.

[tscrim]

NP, I'm happy with your changes and can live with the reversion of the iteritems(). So when you get around to looking at the internal product change and if you're happy with it, you can set this to pos_rev.

[git]

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

​4b32534

further optimizations

[tscrim]

For this change

src/sage/combinat/ncsf_qsym/ncsf.py

@@ -664 +664 @@
                 S = self.realization_of().S()
                 res = S.zero()
                 m = len(xs)
+                ys = [xs[i] - i - 1 for i in range(m)]
                 for s in Permutations(m):
-                    psco = [xs[i] + s[i] - i - 1 for i in range(m)]
+                    psco = [ys[i] + s[i] for i in range(m)]
                     if not all(j >= 0 for j in psco):
                         continue
                     psco2 = [j for j in psco if j != 0]

its (slightly) faster to use enumerate:

ys = [x - i - 1 for i,x in enumerate(xs)]

and

psco = [y + s[i] for i,y in enumerate(ys)]

[darij]

Thanks -- I have somewhat mixed feelings about enumerate when lists can be small, but here it speeds things up (a bit). I'll fix this in my next commit.

[git]

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

​c175a1f

more changes -- please check if I got your algorithm right, Travis

[tscrim]

Remove the 'also' in that reference you changed and then its pos_rev from me.

[git]

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

​5951b6d

final edits

[darij]

OK, so I don't have the time to prove this algorithm, but I see how it works and why it *should* work. Nice idea! I am not replacing the standard internal coproduct method since I don't know the complexities of the two algorithms involved, but it's certainly useful in its existing form already. I assume you're fine with my current changes?

---

New commits:

​5951b6d

final edits

[tscrim]

My implementation is light-years faster (even accounting for bias in my test) than the one via coercion. Try it on compositions of 8 (I got bored and stopped it):

sage: def test(C):
....:     cl,cr = C.random_element(), C.random_element()
....:     print cl
....:     print cr
....:     l,r = Psi[cl], Psi[cr]
....:     %time d1 = Psi.internal_product_on_basis_by_bracketing(cl,cr)
....:     %time d2 = Psi.internal_product(l,r)

sage: C = Compositions(7)
sage: test(C)
[1, 1, 5]
[2, 1, 1, 1, 2]
CPU times: user 20 ms, sys: 0 ns, total: 20 ms
Wall time: 33.2 ms
CPU times: user 44.4 s, sys: 84 ms, total: 44.5 s
Wall time: 53.9 s

So I'm in favor of making the standard algorithm. Would you be good with this?

Your current changes are good.

[darij]

The case I'm worried about is when I is rather long ([1,1,5] doesn't do that trick) and n is in the range not easily tested (between 8 and 12, or so); I'm not sure how well this extends to this case. Here is an example where the bracketing algorithm is considerably slower than the standard one (because the standard one converts to the Complete basis, which is simple for Psi's of spread-out compositions):

sage: Psi[2,1,2,2,1].internal_product(Psi[1,1,1,1,1,1,1,1,1])
0
sage: Psi.internal_product_on_basis_by_bracketing([2,1,2,2,1],[1,1,1,1,1,1,1,1]) 
0

Some hybrid might be good, but I'd rather not make it the default. And I'd rather not do it in this patch :/

Thanks a lot for the optimized algorithm, nevertheless -- I'm positive I'll have a use for it even without having computed its running time.

Would you agree with positive_review?

[tscrim]

I get 2m 45s versus 8s:

sage: %time Psi[2,1,2,2,1].internal_product(Psi[1,1,1,1,1,1,1,1])
CPU times: user 2min 17s, sys: 332 ms, total: 2min 18s
Wall time: 2min 45s
0
sage: %time Psi.internal_product_on_basis_by_bracketing([2,1,2,2,1], [1,1,1,1,1,1,1,1])
CPU times: user 6.61 s, sys: 4 ms, total: 6.62 s
Wall time: 7.99 s
0

Perhaps there was some caching going on that resulted in the speedup? Most of the time spent seems to be in computing the list of integer matrices (which definitely could use optimization). So I'm okay with a positive review here since the bottleneck is not in this code and it should be faster for "long" compositions.

PS - this one seems to be the worst:

sage: %time Psi.internal_product_on_basis_by_bracketing([1,1,1,1,2,2], [1]*8)
CPU times: user 14 s, sys: 56 ms, total: 14 s
Wall time: 17.2 s
0

[darij]

OOPS, I've mucked up the size of the compositions in the test.

Thanks for the positive_review!