Opened 4 years ago
Closed 4 years ago
#25326 closed enhancement (fixed)
Schützenberger anti-automorphisms for WQSym and FQSym; fleshing out FQSym
Reported by: | gh-darijgr | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-8.3 |
Component: | combinatorics | Keywords: | combinatorial hopf algebras, sage-combinat, WQSym |
Cc: | sage-combinat, tscrim, darij, zabrocki, alauve, saliola, amypang, chapoton | Merged in: | |
Authors: | Darij Grinberg | Reviewers: | Travis Scrimshaw |
Report Upstream: | N/A | Work issues: | |
Branch: | a4da76f (Commits, GitHub, GitLab) | Commit: | a4da76f5fb828f389dbb0e68905ba739ff035dec |
Dependencies: | Stopgaps: |
Description (last modified by )
This ticket implements the projection of combinatorial Hopf algebras FQSym -> QSym, a more efficient transition from the M to the F basis on FQSym (using the Möbius function of the weak order on the symmetric groups), and certain involutions of the combinatorial Hopf algebras WQSym and FQSym:
On WQSym:
- The one that, in the M-basis, reverses the ordered set partition, or equivalently complements the packed word (i.e., replaces letters 1,2,...,k by k,k-1,...,1). This is an automorphism of the algebra structure and an anti-automorphism of the coalgebra structure.
- The one that, in the M-basis, complements the (elements of the blocks of the) ordered set partition, or equivalently reverts the packed word. This is an anti-automorphism of the algebra structure (which is obvious if you look at WQSym as a subring of formal power series in non-commutative variables: then it's just a restriction of the anti-automorphism that fixes each letter) and an automorphism of the coalgebra structure.
- The composition of the above two. This is best called the star involution or the Schützenberger anti-automorphism, and is an anti-automorphism of the whole Hopf algebra. Note that this involution restricts to the
star_involution
method of NSym. (The previous two involutions don't restrict to any linear endomorphisms of NSym at all, so we have no caselaw telling us how to call them.)
On FQSym:
The star involution above restricts to FQSym. Also, there are two new involutions on FQSym, one of which corresponds to reversal, and the other to complement; which one depends on the basis. These are NOT restrictions of the analogous involutions of WQSym!
A later ticket, #25541, will implement similar involutions on FSym.
Change History (29)
comment:1 Changed 4 years ago by
- Dependencies #25149 deleted
- Description modified (diff)
comment:2 Changed 4 years ago by
- Branch set to public/ticket/25326
- Commit set to 6c2eca61677c166e122961ba3ce743167f53267c
- Keywords WQSym added
comment:3 Changed 4 years ago by
- Commit changed from 6c2eca61677c166e122961ba3ce743167f53267c to a2abc343a6cdbd4dc35d82548e7b6f915ced57ff
Branch pushed to git repo; I updated commit sha1. New commits:
a2abc34 | another commutative diagram for star_involution
|
comment:4 Changed 4 years ago by
- Commit changed from a2abc343a6cdbd4dc35d82548e7b6f915ced57ff to 405071d81764afe0acc6aaace2338e87092979e0
Branch pushed to git repo; I updated commit sha1. New commits:
405071d | fix coercion bug and override methods on X, Phi and Q bases
|
comment:5 Changed 4 years ago by
- Description modified (diff)
comment:6 Changed 4 years ago by
- Commit changed from 405071d81764afe0acc6aaace2338e87092979e0 to 74696636ea96deab557aa62c146015781f380635
comment:7 Changed 4 years ago by
- Commit changed from 74696636ea96deab557aa62c146015781f380635 to f0642c4dc4e032573a2cf42e15cbb6d138807d48
Branch pushed to git repo; I updated commit sha1. New commits:
f0642c4 | fix doc typo
|
comment:8 Changed 4 years ago by
- Commit changed from f0642c4dc4e032573a2cf42e15cbb6d138807d48 to 7927f38de3d3d57dd56600c38e69f3f8cee00886
Branch pushed to git repo; I updated commit sha1. New commits:
7927f38 | override FQSym's star_involution on Monomial basis
|
comment:9 Changed 4 years ago by
- Commit changed from 7927f38de3d3d57dd56600c38e69f3f8cee00886 to 2412751e81f2b70551efb9023344b0cb5e2c8dae
Branch pushed to git repo; I updated commit sha1. New commits:
2412751 | optimizations (thanks Travis)
|
comment:10 Changed 4 years ago by
- Commit changed from 2412751e81f2b70551efb9023344b0cb5e2c8dae to 00be42ca9c8ccb894b469324936a4c2146c02c29
Branch pushed to git repo; I updated commit sha1. New commits:
00be42c | more doctests for FQSym dendriform structure
|
comment:11 Changed 4 years ago by
- Commit changed from 00be42ca9c8ccb894b469324936a4c2146c02c29 to 03b394586819615a9eb63d73eed4444d0e1ace75
comment:12 Changed 4 years ago by
- Commit changed from 03b394586819615a9eb63d73eed4444d0e1ace75 to 5cc7747cbfead8b6fed9b16badbf5ce76f7e41a6
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
5cc7747 | faster _M_to_F_on_basis for FQSym
|
comment:13 Changed 4 years ago by
I've implemented an explicit M-to-F transition matrix for FQSym as well, as was suggested in one of the TODOs. This speeds up computations for all but the simplest cases (warning: these times are on Cygwin):
Before:
sage: FQSym = algebras.FQSym(ZZ); FQSym.inject_shorthands() Defining F as shorthand for Free Quasi-symmetric functions over Integer Ring in the F basis Defining G as shorthand for Free Quasi-symmetric functions over Integer Ring in the G basis Defining M as shorthand for Free Quasi-symmetric functions over Integer Ring in the Monomial basis sage: %timeit F(M[3,2,1]) 10000 loops, best of 3: 88.2 µs per loop sage: %timeit F(M[1,2,3]) 1000 loops, best of 3: 489 µs per loop sage: %timeit F(M[2,1,3]) 1000 loops, best of 3: 214 µs per loop sage: %timeit F(M[1]) The slowest run took 4.19 times longer than the fastest. This could mean that an intermediate result is being cached. 10000 loops, best of 3: 81 µs per loop sage: %timeit F(M[1,2,3,4]) 100 loops, best of 3: 2.9 ms per loop sage: %timeit F(M[4,2,1,3]) 1000 loops, best of 3: 220 µs per loop sage: %timeit F(M[6,2,5,1,3,4]) 100 loops, best of 3: 2.06 ms per loop sage: %timeit F(M[8,3,2,1,4,5,6,7]) 1 loop, best of 3: 1.66 s per loop
After:
sage: FQSym = algebras.FQSym(ZZ); FQSym.inject_shorthands() Defining F as shorthand for Free Quasi-symmetric functions over Integer Ring in the F basis Defining G as shorthand for Free Quasi-symmetric functions over Integer Ring in the G basis Defining M as shorthand for Free Quasi-symmetric functions over Integer Ring in the Monomial basis sage: %timeit F(M[3,2,1]) 10000 loops, best of 3: 196 µs per loop sage: %timeit F(M[1,2,3]) 1000 loops, best of 3: 243 µs per loop sage: %timeit F(M[2,1,3]) 10000 loops, best of 3: 191 µs per loop sage: %timeit F(M[1]) 10000 loops, best of 3: 136 µs per loop sage: %timeit F(M[1,2,3,4]) 1000 loops, best of 3: 382 µs per loop sage: %timeit F(M[4,2,1,3]) 10000 loops, best of 3: 203 µs per loop sage: %timeit F(M[6,2,5,1,3,4]) 1000 loops, best of 3: 281 µs per loop sage: %timeit F(M[8,3,2,1,4,5,6,7]) 1000 loops, best of 3: 776 µs per loop
comment:14 Changed 4 years ago by
- Commit changed from 5cc7747cbfead8b6fed9b16badbf5ce76f7e41a6 to c5edf7a0b5a1d35fca70ebcb89f3d64a1ea41859
Branch pushed to git repo; I updated commit sha1. New commits:
c5edf7a | further optimization on FQSym
|
comment:15 Changed 4 years ago by
- Commit changed from c5edf7a0b5a1d35fca70ebcb89f3d64a1ea41859 to a418d6969ab3c793f96db58a5192f35b5fccc6aa
Branch pushed to git repo; I updated commit sha1. New commits:
a418d69 | document M-to-F algorithm
|
comment:16 Changed 4 years ago by
- Description modified (diff)
- Status changed from new to needs_review
- Summary changed from Schützenberger anti-automorphisms for WQSym, FQSym, FSym to Schützenberger anti-automorphisms for WQSym and FQSym; fleshing out FQSym
comment:17 Changed 4 years ago by
- Commit changed from a418d6969ab3c793f96db58a5192f35b5fccc6aa to 4312c7217bba52ffb38db343a3457f340f65670b
comment:18 Changed 4 years ago by
- Commit changed from 4312c7217bba52ffb38db343a3457f340f65670b to ebdc81750f4d7c0d28eaa47a99e51e8307342daa
Branch pushed to git repo; I updated commit sha1. New commits:
ebdc817 | Shorter test for TestSuite(FQSym.M()).
|
comment:19 Changed 4 years ago by
- Cc chapoton added
- Reviewers set to Travis Scrimshaw
Frédéric, I wanted to let you know that my previous commit is a fix for the long tests on this ticket.
Also for the new test, here is the top of a %prun
:
60055285 function calls (59625813 primitive calls) in 22.503 seconds Ordered by: internal time ncalls tottime percall cumtime percall filename:lineno(function) 22568202 6.561 0.000 9.473 0.000 combinat.py:930(__eq__) 6564 4.433 0.001 19.148 0.003 tools.py:20(transitive_ideal) 23590175/23590174 3.045 0.000 3.045 0.000 {isinstance} 360076 1.124 0.000 2.176 0.000 permutation.py:483(__init__) 180428 0.830 0.000 4.829 0.000 permutation.py:3772(permutohedron_succ) 188037 0.577 0.000 0.882 0.000 free_module.py:1049(_monomial) 360076 0.556 0.000 0.855 0.000 combinat.py:1256(__init__) 2399452 0.507 0.000 0.909 0.000 combinat.py:1201(index) 180428 0.483 0.000 1.144 0.000 permutation.py:3805(<lambda>) 2417264 0.406 0.000 0.406 0.000 {method 'index' of 'list' objects}
So about 1/2 of the time is spent just checking that two permutations are equal.
comment:20 Changed 4 years ago by
Thanks, Travis!
comment:21 Changed 4 years ago by
- Commit changed from ebdc81750f4d7c0d28eaa47a99e51e8307342daa to 2d9259a0ace7e631a111fa8110efcb32be01fafc
Branch pushed to git repo; I updated commit sha1. New commits:
2d9259a | Some last fixes.
|
comment:22 Changed 4 years ago by
Thinking more about the doc, I don't like the fact that the definitions are in one category file that is basically overwritten in the special cases. So the documentation is not well localized. Although one of the annoying things is it would require a fair bit of duplication. So I am inclined to let it be.
Thus, if my changes are good, then positive review.
comment:23 Changed 4 years ago by
- Commit changed from 2d9259a0ace7e631a111fa8110efcb32be01fafc to 4d071302cd0f6de49b97f757027eaabeb1d14639
Branch pushed to git repo; I updated commit sha1. New commits:
4d07130 | Tweaks from talking with Darij.
|
comment:24 Changed 4 years ago by
- Commit changed from 4d071302cd0f6de49b97f757027eaabeb1d14639 to 6517a1c0c741bbfb526848a60dc120bb1feee80b
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
6517a1c | Tweaks from talking with Darij.
|
comment:25 Changed 4 years ago by
- Commit changed from 6517a1c0c741bbfb526848a60dc120bb1feee80b to ea86580d33a64fb979b177200d5966f099c3662b
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
ea86580 | Tweaks from talking with Darij.
|
comment:26 Changed 4 years ago by
- Commit changed from ea86580d33a64fb979b177200d5966f099c3662b to 5e768bde77319830883074199cf1d524932e041e
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
5e768bd | Tweaks from talking with Darij.
|
comment:27 Changed 4 years ago by
- Commit changed from 5e768bde77319830883074199cf1d524932e041e to a4da76f5fb828f389dbb0e68905ba739ff035dec
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
a4da76f | Tweaks from talking with Darij.
|
comment:28 Changed 4 years ago by
- Status changed from needs_review to positive_review
Thanks, Travis! Newest version of your commit looks good.
comment:29 Changed 4 years ago by
- Branch changed from public/ticket/25326 to a4da76f5fb828f389dbb0e68905ba739ff035dec
- Resolution set to fixed
- Status changed from positive_review to closed
WQSym part has been implemented, at least on the M basis. I have formulas for all other basis except for C, but I haven't overridden the method so far, to avoid duplicating documentation. (I'm not actually sure if the overrides will significantly speed up the computation, except for the star involution -- since the other two involutions don't involve cancellations when you go through the M basis.)
New commits:
reversal and complement on ordered set partitions
algebraic complement on WQSym
coalgebraic complement on WQSym
star involution on WQSym
trivial pyflakes change