Opened 8 years ago
Closed 8 years ago
#15949 closed defect (fixed)
Involutions on NSym and QSym part II
Reported by:  darij  Owned by:  

Priority:  major  Milestone:  sage6.2 
Component:  combinatorics  Keywords:  partitions, symmetric functions, NSym, QSym, NCSF, Kronecker product, 
Cc:  zabrocki, tscrim, sagecombinat  Merged in:  
Authors:  Darij Grinberg  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  5951b6d (Commits, GitHub, GitLab)  Commit:  5951b6d429c94fcba5f1c235be3465fdb845766a 
Dependencies:  Stopgaps: 
Description
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 tcompletion of a partition (formerly in #15825);
 improvements on the to_dyck_word method on partitions (formerly in #15825).
Change History (21)
comment:1 Changed 8 years ago by
 Status changed from new to needs_review
comment:2 Changed 8 years ago by
 Commit changed from 13e33bf1e777054945e4f2029ca7fb5435347132 to fea174380b38e80c5e4b1b40f8ea587e3f47ea86
comment:3 Changed 8 years ago by
 Commit changed from fea174380b38e80c5e4b1b40f8ea587e3f47ea86 to bff955a9236bb86f6a8ea35a7dff12f4a62cfefa
Branch pushed to git repo; I updated commit sha1. New commits:
bff955a  more bugfixes

comment:4 Changed 8 years ago by
 Commit changed from bff955a9236bb86f6a8ea35a7dff12f4a62cfefa to c98d3006a7ef3fc874327d2b4dd16a541b69220e
comment:5 Changed 8 years ago by
Hey Darij,
I've made some review changes, (minor) optimizations, and rewrote the algorithm for the internal product from bracketing using a backtracing^{2} 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
comment:6 Changed 8 years ago by
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:
for m, c in self.monomial_coefficients().items()
is indeed slower thanfor m, c in self
(thanks for making me aware of this!), butfor m, c in self.monomial_coefficients().iteritems()
is not (although the difference is very small). I still preferfor m, c in self
for brevity, but where theiteritems
syntax was used I've put it back.
comment:7 Changed 8 years ago by
 Commit changed from c98d3006a7ef3fc874327d2b4dd16a541b69220e to a9c74b4638c69a469610f35128eb4811ed72b7a4
comment:8 Changed 8 years ago by
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.
comment:9 Changed 8 years ago by
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.
comment:10 Changed 8 years ago by
 Commit changed from a9c74b4638c69a469610f35128eb4811ed72b7a4 to 4b32534514e8d19378dc4b3dce6808190c12d6af
Branch pushed to git repo; I updated commit sha1. New commits:
4b32534  further optimizations

comment:11 Changed 8 years ago by
For this change

src/sage/combinat/ncsf_qsym/ncsf.py
diff git a/src/sage/combinat/ncsf_qsym/ncsf.py b/src/sage/combinat/ncsf_qsym/ncsf.py index 36eecd9..c7b0849 100644
a b class NonCommutativeSymmetricFunctions(UniqueRepresentation, Parent): 664 664 S = self.realization_of().S() 665 665 res = S.zero() 666 666 m = len(xs) 667 ys = [xs[i]  i  1 for i in range(m)] 667 668 for s in Permutations(m): 668 psco = [ xs[i] + s[i]  i  1for i in range(m)]669 psco = [ys[i] + s[i] for i in range(m)] 669 670 if not all(j >= 0 for j in psco): 670 671 continue 671 672 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)]
comment:12 Changed 8 years ago by
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.
comment:13 Changed 8 years ago by
 Commit changed from 4b32534514e8d19378dc4b3dce6808190c12d6af to c175a1f74993cfb386952591048c1f0215f8bc6e
Branch pushed to git repo; I updated commit sha1. New commits:
c175a1f  more changes  please check if I got your algorithm right, Travis

comment:14 Changed 8 years ago by
Remove the 'also' in that reference you changed and then its pos_rev from me.
comment:15 Changed 8 years ago by
 Commit changed from c175a1f74993cfb386952591048c1f0215f8bc6e to 5951b6d429c94fcba5f1c235be3465fdb845766a
Branch pushed to git repo; I updated commit sha1. New commits:
5951b6d  final edits

comment:16 Changed 8 years ago by
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

comment:17 Changed 8 years ago by
My implementation is lightyears 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.
comment:18 Changed 8 years ago by
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 spreadout 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?
comment:19 Changed 8 years ago by
 Reviewers set to Travis Scrimshaw
 Status changed from needs_review to positive_review
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
comment:20 Changed 8 years ago by
OOPS, I've mucked up the size of the compositions in the test.
Thanks for the positive_review!
comment:21 Changed 8 years ago by
 Branch changed from public/combinat/involnsym2 to 5951b6d429c94fcba5f1c235be3465fdb845766a
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
leftpadded Kronecker product on Sym too, and fixes for my own bugs: