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: sage-6.2
Component: combinatorics Keywords: partitions, symmetric functions, NSym, QSym, NCSF, Kronecker product,
Cc: zabrocki, tscrim, sage-combinat Merged in:
Authors: Darij Grinberg Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 5951b6d (Commits, GitHub, GitLab) Commit: 5951b6d429c94fcba5f1c235be3465fdb845766a
Dependencies: Stopgaps:

Status badges

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 t-completion 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 darij

  • Status changed from new to needs_review

comment:2 Changed 8 years ago by git

  • Commit changed from 13e33bf1e777054945e4f2029ca7fb5435347132 to fea174380b38e80c5e4b1b40f8ea587e3f47ea86

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

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

comment:3 Changed 8 years ago by git

  • Commit changed from fea174380b38e80c5e4b1b40f8ea587e3f47ea86 to bff955a9236bb86f6a8ea35a7dff12f4a62cfefa

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

bff955amore bugfixes

comment:4 Changed 8 years ago by git

  • Commit changed from bff955a9236bb86f6a8ea35a7dff12f4a62cfefa to c98d3006a7ef3fc874327d2b4dd16a541b69220e

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

f082858Merge branch 'public/combinat/invol-nsym-2' of trac.sagemath.org:sage into public/combinat/invol-nsym-2
c98d300Review changes and (minor) optimizations.

comment:5 Changed 8 years ago by tscrim

Hey Darij,

I've made some review changes, (minor) optimizations, and rewrote the algorithm for the internal product from bracketing using a backtracing2 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

Last edited 8 years ago by tscrim (previous) (diff)

comment:6 Changed 8 years ago by 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.
  1. 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).

comment:7 Changed 8 years ago by git

  • Commit changed from c98d3006a7ef3fc874327d2b4dd16a541b69220e to a9c74b4638c69a469610f35128eb4811ed72b7a4

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

31271dfMerge branch 'public/combinat/invol-nsym-2' of git://trac.sagemath.org/sage into nsym
262bea1Merge branch 'public/combinat/invol-nsym-2' of git://trac.sagemath.org/sage into nsym
a9c74b4more optimizations

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

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

comment:10 Changed 8 years ago by git

  • Commit changed from a9c74b4638c69a469610f35128eb4811ed72b7a4 to 4b32534514e8d19378dc4b3dce6808190c12d6af

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

4b32534further optimizations

comment:11 Changed 8 years ago by tscrim

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): 
    664664                S = self.realization_of().S()
    665665                res = S.zero()
    666666                m = len(xs)
     667                ys = [xs[i] - i - 1 for i in range(m)]
    667668                for s in Permutations(m):
    668                     psco = [xs[i] + s[i] - i - 1 for i in range(m)]
     669                    psco = [ys[i] + s[i] for i in range(m)]
    669670                    if not all(j >= 0 for j in psco):
    670671                        continue
    671672                    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 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.

comment:13 Changed 8 years ago by git

  • Commit changed from 4b32534514e8d19378dc4b3dce6808190c12d6af to c175a1f74993cfb386952591048c1f0215f8bc6e

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

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

comment:14 Changed 8 years ago by tscrim

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

comment:15 Changed 8 years ago by git

  • Commit changed from c175a1f74993cfb386952591048c1f0215f8bc6e to 5951b6d429c94fcba5f1c235be3465fdb845766a

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

5951b6dfinal edits

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

5951b6dfinal edits

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

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

comment:19 Changed 8 years ago by tscrim

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

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

Thanks for the positive_review!

Last edited 8 years ago by darij (previous) (diff)

comment:21 Changed 8 years ago by vbraun

  • Branch changed from public/combinat/invol-nsym-2 to 5951b6d429c94fcba5f1c235be3465fdb845766a
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.